文献

J-GLOBAL ID：201502227462869413   整理番号：15A0367922

Z₃ラベル付きグラフにおける指定ラベルs-tパスの発見

著者 (3件)： 河瀬康志 (東京工大 大学院社会理工学研究科) ,  小林佑輔 (東大 大学院情報理工学系研究科) ,  山口勇太郎 (東大 大学院情報理工学系研究科)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2014  号： AL-149  ページ： VOL.2014-AL-149,NO.1 (WEB ONLY)  発行年： 2014年09月05日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： パスや閉路の長さの偶奇に関する問題は,グラフ理論や理論計算機科学の分野において,古典的でよく研究されてきた話題である。この種の基本的な問題として,たとえば,無向グラフにおいて指定された2点s,t間を結ぶ奇数長(または偶数長)のパスを見つける問題が挙げられる。この問題は多項式時間で容易に解けるが,一方で,有向グラフにおける同じ問題はNP困難であることも知られている。本稿では,この種の問題の一般化として,群ラベル付きグラフにおいて指定されたラベルのs-tパスを見つける問題を考える。ここで,群ラベル付きグラフとは,各枝が群の要素によってラベル付けされている有向グラフを指す。無向グラフにおいて奇数長(または偶数長)のパスを見つける問題は,Z₂ラベル付きグラフにおいてラベルが1(または0)のパスを見つける問題として定式化できる。近年,群ラベル付きグラフにおいて,ある条件を満たすラベル非零のパスや閉路を見つけるいくつかの問題に対し,効率的なアルゴリズムが提案されている。一方で,指定したラベルのパスを見つける問題の難しさは,ラベルに用いられる群に強く依存する。たとえば,群がZの場合,指定したラベルのs-tパスの存在判定問題はNP完全であるが,群がZ₂の場合は極めて簡単に解ける。したがって,位数を固定した有限群の場合の計算複雑性は興味深い話題であり,Z₃が最初の非自明な場合である。また,群がZ₃の場合には,指定したラベルのs-tパスを見つける問題は無向グラフにおける2点素パス問題の一般化になっており,この問題が多項式時間で解けるという事実も本研究の動機の一端を担っている。本稿では,2点s,tを指定したZ₃ラベル付きグラフが,指定したラベルのs-tパスを持つ必要十分条件を与える。また,その特徴付けに基づき,s-tパスの取り得るラベルを計算し,各ラベルを持つs-tパスを求める多項式時間アルゴリズムを提案する。(著者抄録)

シソーラス用語： *グラフ理論 ,  *NP完全問題 ,  計算量理論 ,  有向グラフ ,  無向グラフ ,  ラベリング ,  経路探索 ,  閉路 ,  偶数 ,  奇数 ,  計算機科学 ,  アルゴリズム ,  計算量 ,  多項式 ,  NP困難
準シソーラス用語： *NP完全 ,  ラベル付与 ,  多項式時間アルゴリズム ,  理論計算機科学

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

引用文献 (10件)：

• M. Chudnovsky, J. Geelen, B. Gerards, L. Goddyn, M. Lohman, P. D. Seymour: Packing non-zero A-paths in group-labelled graphs, Combinatorica, 26 (2006), 521-532.
• M. Chudnovsky, W. Cunningham, J. Geelen: An algorithm for packing non-zero A-paths in group-labelled graphs, Combinatorica, 28 (2008), 145-161.
• R. Diestel: Graph Theory 4th ed., Springer-Verlag, Heidelberg, 2010.
• T. Huynh: The Linkage Problem for Group-Labelled Graphs, Ph.D. Thesis, Department of Combinatorics and Optimization, University of Waterloo, Ontario, 2009.
• K. Kawarabayashi, P. Wollan: Non-zero disjoint cycles in highly connected group labelled graphs, Journal of Combinatorial Theory, Ser. B, 96 (2006), 296-301.

タイトルに関連する用語 (4件)： ラベル ,  グラフ ,  パス ,  発見