The search functionality is under construction.
The search functionality is under construction.

A Note on Enumeration of 3-Edge-Connected Spanning Subgraphs in Plane Graphs

Yasuko MATSUI, Kenta OZEKI

  • Full Text Views

    0

  • Cite this

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