高度エッジ接続スパニング部分グラフの列挙

YAMANAKA Katsuhisa; MATSUI Yasuko; NAKANO Shin-ichi

文献

J-GLOBAL ID：201902250191114923 整理番号：19A2479707

高度エッジ接続スパニング部分グラフの列挙

Enumerating Highly-Edge-Connected Spanning Subgraphs

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

著者 (3件)： , ,
資料名：
巻： E102.A 号： 9 ページ： 1002-1006(J-STAGE) 発行年： 2019年
JST資料番号： U0466A ISSN： 1745-1337 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：英語 (EN)

本論文では,著者らは入力グラフの高いエッジ接続性を有するスパニング部分グラフを列挙する問題を検討した。このような部分グラフは,2つの頂点間の複数の経路を確実にする。著者らは,最初に,n個の頂点を有する与えられた平面グラフのすべての2エッジ接続スパニング部分グラフを列挙するアルゴリズムを提示した。アルゴリズムは,O(n)時間で入力グラフの各2エッジ接続スパニング部分グラフを生成した。著者らは次に,mエッジを持つ与えられた一般的グラフのすべてのkエッジ接続スパニング部分グラフを列挙するアルゴリズムを提示した。このアルゴリズムは,O(mT)時間で入力グラフの各kエッジ接続スパニング部分グラフを生成したが,ここで,Tはグラフのkエッジ接続性をチェックするための実行時間である。(翻訳著者抄録)

, , , , , ,

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

グラフ理論基礎

引用文献 (17件)：

[1] D. Avis and K. Fukuda, “Reverse search for enumeration,” Discrete Appl. Math., vol.65, no.1-3, pp.21-46, 1996. 10.1016/0166-218x(95)00026-n
[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, pp.1884-1896, Jan. 2012. 10.1137/1.9781611973105.134
[3] E. Boros, K. Borys, K.M. Elbassioni, V. Gurvich, K. Makino, and G. Rudolf, “Generating minimal k-vertex connected spanning subgraphs,” Proc. 13th Annual International Computing and Combinatorics Conference, pp.222-231, 2007. 10.1007/978-3-540-73545-8_23
[4] A. Conte, M.M. Kanté, Y. Otachi, T. Uno, and K. Wasa, “Efficient enumeration of maximal k-degenerate subgraphs in a chordal graph,” Proc. 23rd Annual International Computing and Combinatorics Conference, pp.150-161, 2017. 10.1007/978-3-319-62389-4_13
[5] A. Conte, R.D. Virgilio, A. Maccioni, M. Patrignani, and R. Torlone, “Finding all maximal cliques in very large social networks,” Proc. 19th International Conference on Extending Database Technology, pp.173-184, 2016.

, ,

前のページに戻る