The search functionality is under construction.

The search functionality is under construction.

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*(*n*^{2}) 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

Yasuko MATSUI

Tokai University

Kenta OZEKI

Yokohama National University

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.

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*(*n*^{2}) 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*(*n*^{2}) 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*(*n*^{2}) time. This time complexity is the same as the algorithm by Yamanaka et al., but our algorithm is simpler than theirs.

ER -