IEICE TRANSACTIONS on Information
A Note on Enumeration of 3-Edge-Connected Spanning Subgraphs in Plane Graphs
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E104-D No.3 pp.389-391
- Publication Date
- 2021/03/01
- Publicized
- 2020/10/07
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2020FCL0002
- Type of Manuscript
- Special Section LETTER (Special Section on Foundations of Computer Science — New Trends of Theory of Computation and Algorithm —)
- Category
Authors
Yasuko MATSUI
Tokai University
Kenta OZEKI
Yokohama National University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yasuko MATSUI, Kenta OZEKI, "A Note on Enumeration of 3-Edge-Connected Spanning Subgraphs in Plane Graphs" in IEICE TRANSACTIONS on Information,
vol. E104-D, no. 3, pp. 389-391, March 2021, doi: 10.1587/transinf.2020FCL0002.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2020FCL0002/_p
Copy
@ARTICLE{e104-d_3_389,
author={Yasuko MATSUI, Kenta OZEKI, },
journal={IEICE TRANSACTIONS on Information},
title={A Note on Enumeration of 3-Edge-Connected Spanning Subgraphs in Plane Graphs},
year={2021},
volume={E104-D},
number={3},
pages={389-391},
abstract={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.},
keywords={},
doi={10.1587/transinf.2020FCL0002},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - A Note on Enumeration of 3-Edge-Connected Spanning Subgraphs in Plane Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 389
EP - 391
AU - Yasuko MATSUI
AU - Kenta OZEKI
PY - 2021
DO - 10.1587/transinf.2020FCL0002
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E104-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2021
AB - 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.
ER -
English
