-
- YAMANAKA Katsuhisa
- Faculty of Science and Engineering, Iwate University
-
- MATSUI Yasuko
- School of Science, Tokai University
-
- NAKANO Shin-ichi
- School of Science and Technology, Gunma University
抄録
<p>In this paper, we consider the problem of enumerating spanning subgraphs with high edge-connectivity of an input graph. Such subgraphs ensure multiple routes between two vertices. We first present an algorithm that enumerates all the 2-edge-connected spanning subgraphs of a given plane graph with n vertices. The algorithm generates each 2-edge-connected spanning subgraph of the input graph in O(n) time. We next present an algorithm that enumerates all the k-edge-connected spanning subgraphs of a given general graph with m edges. The algorithm generates each k-edge-connected spanning subgraph of the input graph in O(mT) time, where T is the running time to check the k-edge-connectivity of a graph.</p>
収録刊行物
-
- IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
-
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E102.A (9), 1002-1006, 2019-09-01
一般社団法人 電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390001277344645760
-
- NII論文ID
- 130007699444
-
- ISSN
- 17451337
- 09168508
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- Crossref
- CiNii Articles
- KAKEN
-
- 抄録ライセンスフラグ
- 使用不可