文献

J-GLOBAL ID：201802221980141059   整理番号：18A1846579

長さ4のサイクルのないグラフにおける誘導マッチングの効率的列挙

Efficient Enumeration of Induced Matchings in a Graph without Cycles with Length Four

著者 (4件)： KURITA Kazuhiro (IST, Hokkaido University) ,  WASA Kunihiro (National Institute of Informatics) ,  UNO Takeaki (National Institute of Informatics) ,  ARIMURA Hiroki (IST, Hokkaido University)
資料名： IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Web)  (IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Web))
巻： E101.A  号： 9  ページ： 1383-1391(J-STAGE)  発行年： 2018年 
JST資料番号： U0466A  ISSN： 1745-1337  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本研究で筆者らは,誘導マッチング列挙に関連する問題に取り組んだ。エッジ集合MはグラフG=(V,E)の誘導マッチングである。マッチングの列挙は文献で広く研究されている;しかしながら,誘導マッチングに関する研究はほとんどない。直接アルゴリズムは,各解に対し部分問題を生成する時間から来るO(Δ²)時間かかり,そこではΔが入力グラフの最大次数である。部分問題を生成するために,アルゴリズムはエッジeを上げて,2つのグラフを生成して,1つはGからeを取り除くことによって得て,他はe,eの隣接エッジそしてeの隣接エッジの隣接エッジを取り除くことによって得た。この操作はO(Δ²)時間を必要とするので,直接アルゴリズムは解当たりO(Δ²)時間で全ての誘導マッチングを列挙した。筆者らは短時間で部分問題を生成することを可能にする局所構造を研究し,入力グラフがC₄フリーであるならば,時間計算量がO(1)であることを証明した。グラフは,そのどの部分グラフも長さ4のサイクルを持たない場合に限って,C₄フリーである。(翻訳著者抄録)

シソーラス用語： サイクル ,  *グラフ ,  *誘導 ,  *マッチング ,  端部 ,  集合 ,  問題 ,  構造 ,  計算量 ,  部分グラフ
準シソーラス用語： エッジ ,  局所構造 ,  時間計算量 ,  部分問題

著者キーワード (4件)： 列挙アルゴリズム ,  誘導部分グラフ ,  誘導マッチング ,  一定の修正時間列挙

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (22件)：

• [1] N. Alon, D. Reichman, I. Shinkar, T. Wagner, S. Musslick, J.D. Cohen, T. Griffiths, B. Dey, and K. Özcimder, “A graph-theoretic approach to multitasking,” Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, pp.2097-2106, Long Beach, CA, USA, Dec. 2017.
• [2] H. Balakrishnan, C.L. Barrett, V.A. Kumar, M.V. Marathe, and S. Thite, “The distance-2 matching problem and its relationship to the mac-layer capacity of ad hoc wireless networks,” IEEE J. Sel. Areas Commun., vol.22, no.6, pp.1069-1079, 2004. 10.1109/jsac.2004.830909
• [3] A. Brandstädt and C.T. Hoàng, “Maximum induced matchings for chordal graphs in linear time,” Algorithmica, vol.52, no.4, pp.440-447, 2008. 10.1007/s00453-007-9045-2
• [4] K. Cameron, “Induced matchings,” Discrete Appl. Math., vol.24, no.1-3, pp.97-102, 1989. 10.1016/0166-218x(92)90275-f
• [5] R. Curticapean and D. Marx, “Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts,” Proc. FOCS 2014, pp.130-139, IEEE, 2014. 10.1109/focs.2014.22

タイトルに関連する用語 (4件)： サイクル ,  グラフ ,  誘導 ,  マッチング