文献

J-GLOBAL ID：202302284781350187   整理番号：23A0146409

平面グラフ中の辺連結度制約付き全域部分グラフの効率良い列挙

Efficient Enumeration of Spanning Subgraphs in Planar Graphs with Edge Connectivity Constraints

著者 (3件)： KOBAYASHI Yasuaki (Hokkaido Univ., Hokkaido, JPN) ,  KURITA Kazuhiro (Nagoya Univ., Aichi, JPN) ,  WASA Kunihiro (Hosei Univ., Tokyo, JPN)
資料名： 電子情報通信学会技術研究報告(Web)  (IEICE Technical Report (Web))
巻： 122  号： 229(COMP2022 13-20)  ページ： 21-28 (WEB ONLY)  発行年： 2022年10月19日 
JST資料番号： U2030A  ISSN： 2432-6380  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文では,我々は平面グラフ中の辺連結度制約付き全域部分グラフの列挙問題に取り組む.この問題に対し,我々は二つの効率良い列挙アルゴリズム与える.最初のアルゴリズムは平面グラフ中の全てのk辺連結な全域部分グラフをならし線形時間と線形領域で列挙するアルゴリズムである.もう一つのアルゴリズムは極小な2辺連結全域部分グラフを多項式遅延と指数領域で列挙するアルゴリズムである.(著者抄録)

シソーラス用語： *数え上げ理論 ,  制約付最適化問題 ,  *平面グラフ ,  *部分グラフ ,  アルゴリズム ,  グラフ ,  スパンニング木
準シソーラス用語： 線形時間アルゴリズム ,  連結グラフ

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

引用文献 (17件)：

• Endre Boros, Konrad Borys, Khaled M. Elbassioni, Vladimir Gurvich, Kazuhisa Makino, and Gábor Rudolf. Generating minimal k-vertex connected spanning subgraphs. In Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings, pages 222-231, 2007.
• Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, and Leonid Khachiyan. Enumerating minimal dicuts and strongly connected subgraphs and related geometric problems. In Integer Programming and Combinatorial Optimization, 10th International IPCO Conference, New York, NY, USA, June 7-11, 2004, Proceedings, pages 152-162,2004.
• Hsien-Chih Chang and Hsueh-I Lu. Computing the girth of a planar graph in linear time. SIAM J. Comput., 42(3):1077-1094, 2013.
• Sara Cohen, Benny Kimelfeld, and Yehoshua Sagiv. Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties. J. Comput. Syst. Sci., 74(7):1147-1159, 2008.
• Alessio Conte and Takeaki Uno. New polynomial delay bounds for maximal subgraph enumeration by proximity search. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1179-1190,2019.

タイトルに関連する用語 (4件)： 平面グラフ ,  辺 ,  制約 ,  部分グラフ