2辺連結誘導部分グラフ数え上げのための多項式遅延アルゴリズム

ITO Taishu; SANO Yusuke; YAMANAKA Katsuhisa; HIRAYAMA Takashi

文献

J-GLOBAL ID：202202277477647229 整理番号：22A1077274

2辺連結誘導部分グラフ数え上げのための多項式遅延アルゴリズム

A Polynomial Delay Algorithm for Enumerating 2-Edge-Connected Induced Subgraphs

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=22A1077274&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=22A1077274&from=J-GLOBAL&jstjournalNo=U0469A") }}

著者 (4件)： , , ,
資料名：
巻： E105.D 号： 3 ページ： 466-473(J-STAGE) 発行年： 2022年
JST資料番号： U0469A ISSN： 1745-1361 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：英語 (EN)

与えられたグラフの連結誘導部分グラフを数え上げる問題は古典的であり,よく研究されている。連結誘導部分グラフは,各部分グラフに対して一定時間で数え上げのできることが知られている。本論文では,高度に連結された誘導部分グラフに焦点を当てた。グラフに関する連結性の最も主要な概念は頂点連結性である。頂点連結性に関して,k-頂点連結スパニング部分グラフなど,いくつかの数え上げ問題の設定と数え上げアルゴリズムが提案されてきた。本論文では,グラフ連結性のもう一つの主要な概念である辺連結性に焦点を当てた。これは,道路網で避難経路を見つける問題によって動機づけられている。避難経路では,高度に辺が連結された部分グラフが,2つの頂点間の複数の経路を確実にするため,辺連結性は重要である。本論文では,与えられたグラフの2辺連結誘導部分グラフを数え上げる問題について考察した。n個の頂点とm個の辺を持つ入力グラフGの2辺連結誘導部分グラフを数え上げるアルゴリズムを提案した。S_GがGの2辺連結誘導部分グラフの集合であるとき,本アルゴリズムは,O(n³m|S_G|)時間ですべての2辺連結誘導部分グラフを数え上げる。さらに,本アルゴリズムをわずかに修正することにより,2辺連結誘導部分グラフのO(n³m)遅延数え上げアルゴリズムを得た。(翻訳著者抄録)

, , , , ,

著者キーワード (4件)： , , ,

グラフ理論基礎

引用文献 (25件)：

[1] Y. Sano, K. Yamanaka, and T. Hirayama, “A polynomial delay algorithm for enumerating 2-edge-connected induced subgraphs,” Frontiers in Algorithmics-14th International Workshop, FAW 2020, Haikou, China, Oct. 19-21, 2020, Proceedings, ed. M. Li, Lecture Notes in Computer Science, vol.12340, pp.13-24, Springer, 2020. 10.1007/978-3-030-59901-0_2
[2] E. Birmelé, R. Ferreira, R. Grossi, A. Marino, N. Pisanti, R. Rizzi, and G. Sacomoto, “Optimal Listing of Cycles and st-Paths in Undirected Graphs,” Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pp.1884-1896, Jan. 2012. 10.1137/1.9781611973105.134
[3] R. Ferreira, R. Grossi, R. Rizzi, G. Sacomoto, and M.F. Sagot, “Amortized ~O(|V|)-delay algorithm for listing chordless cycles in undirected graphs,” Proc. 22nd European Symposium on Algorithms (ESA 2014), Lecture Notes in Computer Science, vol.8737, pp.418-429, 2014. 10.1007/978-3-662-44777-2_35
[4] R.C. Read and R.E. Tarjan, “Bounds on backtrack algorithms for listing cycles, paths, and spanning trees,” Networks, vol.5, no.3, pp.237-252, 1975. 10.1002/net.1975.5.3.237
[5] T. Uno and H. Satoh, “An efficient algorithm for enumerating chordless cycles and chordless paths,” Proc. 17th International Conference on Discovery Science (DS 2014), vol.8777, pp.313-324, 2014. 10.1007/978-3-319-11812-3_27

, , , , ,

前のページに戻る