文献

J-GLOBAL ID：202202260117444832   整理番号：22A1047269

グラフクラスにおけるサイクル可能性【JST・京大機械翻訳】

Cyclability in graph classes

著者 (2件)： Crespelle Christophe (Universite Claude Bernard Lyon 1, INRIA, Lyon, France) ,  Golovach Petr A. (Department of Informatics, University of Bergen, Norway)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 313  ページ： 147-178  発行年： 2022年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフGの頂点の部分集合T|ΔV(G)は,もしGがTのあらゆる頂点を含むサイクルCを持つならば,サイクブルであると言われ,そして,正の整数kのために,グラフGは,大部分のkにおけるサイズの頂点のあらゆる集合がサイクブルであるならば,k-cycableであった。グラフGと頂点のセットT,Tがサイクブルであるかどうか,およびGがk-サイクブルであるかどうか,グラフGと正の整数kを与えるk-Cyclbility問題kask,を与えられた,末端Cyclability問題kasksは,頂点のグラフGと集合Tを与えられた。これらの問題は古典的ハミルトニアンサイクル問題の一般化である。ハミルトニアンサイクルに対して多項式アルゴリズムをアドミットするグラフクラスに対するこれらの問題の研究を開始した。間隔グラフ,二部置換グラフおよびグラフに対する線形時間において,末端Cyclbilityを解決できることを示した。さらに,著者らは,サイクルである解を生成するか,または,無回答を認証するグラフ分離器を出力する,証明アルゴリズムを構築した。これらの結果を用いて,前述のグラフクラスに制約されたとき,k-Cyclableを多項式時間で解くことができることを示した。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： ハミルトニアン ,  アルゴリズム ,  *グラフ ,  分離装置 ,  *サイクル ,  計算理論 ,  線形性 ,  集合 ,  問題 ,  整数 ,  部分集合 ,  頂点 ,  認証
準シソーラス用語： 区間グラフ ,  多項式時間 ,  多項式アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (5件)： サイクル性 ,  区間グラフ ,  二部置換グラフ ,  コグラフ ,  認証アルゴリズム

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (4件)： グラフ ,  クラス ,  サイクル ,  可能性