-
- MATSUI Yasuko
- School of Science, Tokai University
-
- OZEKI Kenta
- Faculty of Environment and Information Sciences, Yokohama National University
抄録
<p>This paper deals with the problem of enumerating 3-edge-connected spanning subgraphs of an input plane graph. In 2018, Yamanaka et al. proposed two enumeration algorithms for such a problem. Their algorithm generates each 2-edge-connected spanning subgraph of a given plane graph with n vertices in O(n) time, and another one generates each k-edge-connected spanning subgraph of a general graph with m edges in O(mT) time, where T is the running time to check the k-edge connectivity of a graph. This paper focuses on the case of the 3-edge-connectivity in a plane graph. We give an algorithm which generates each 3-edge-connected spanning subgraph of the input plane graph in O(n2) time. This time complexity is the same as the algorithm by Yamanaka et al., but our algorithm is simpler than theirs.</p>
収録刊行物
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E104.D (3), 389-391, 2021-03-01
一般社団法人 電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390005822570111360
-
- NII論文ID
- 130007993194
-
- ISSN
- 17451361
- 09168532
-
- 本文言語コード
- en
-
- データソース種別
-
- JaLC
- Crossref
- CiNii Articles
- KAKEN
-
- 抄録ライセンスフラグ
- 使用不可