半エッジを持つ正則マルチグラフのリスト被覆【JST・京大機械翻訳】

Bok Jan; Fiala Jiri; Jedlickova Nikola; Kratochvil Jan; Rzazewski Pawel

プレプリント

J-GLOBAL ID：202202211425402213 整理番号：22P0328702

半エッジを持つ正則マルチグラフのリスト被覆【JST・京大機械翻訳】

List covering of regular multigraphs with semi-edges

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (5件)： , , , ,
資料名：
発行年： 2022年04月08日プレプリントサーバーでの情報更新日： 2023年06月10日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

トポロジーグラフ理論における最近の開発に沿って,著者らは,{em多重エッジ},{emループ},および{em半エッジ}を含むことができる無向グラフを考察した。グラフは,もし半エッジ,ループ無し,および多重エッジを含まないならば,{em単純}と呼ばれる。また,局所バイジェクティブホモモルフィズムとして知られているグラフカバー投影は,入射を保存し,あらゆる頂点のエッジ近傍における局所バイジェクションである2つのグラフの頂点とエッジの間のマッピングである。この概念はトポロジーグラフ理論から生じるが,結合器と理論的コンピュータ科学における応用も見出す。2より大きい原子価のあらゆる固定単純正規グラフHに対して,入力グラフがHをカバーするかどうかはNP完全であることが知られている。半エッジを有するグラフは,最近,この文脈で考慮され,そのようなグラフをカバーする複雑性に関する部分的結果だけが,これまで知られている。本論文では,入力グラフの頂点とエッジが許容可能な目標のリストを持つ,List-H-Coverと呼ばれる問題のリストバージョンを考察した。主な結果は,List-H-Cover問題は,少なくとも1つの半単純頂点(すなわち,ループなしで入射する頂点,多重エッジ無し,およびほとんどの1つの半エッジを有する)を含む,2より大きい原子価の全ての正規グラフHに対してNP完全であると読む。この結果を用いて,著者らは,List-H-Coverの計算量のためのNP-co/polytime dichotomyを示した。【JST・京大機械翻訳】

, , , , , , , , , , , ,
, , , 【Automatic Indexing@JST】

グラフ理論基礎

, , ,

前のページに戻る