[Updated on Apr. 18] Integration of CiNii Articles into CiNii Research

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

  • MATSUI Yasuko
    School of Science, Tokai University
  • OZEKI Kenta
    Faculty of Environment and Information Sciences, Yokohama National University

Abstract

<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>

Journal

Citations (0)*help

See more

References(8)*help

See more

Related Articles

See more

Related Data

See more

Related Books

See more

Related Dissertations

See more

Related Projects

See more

Related Products

See more

Details

Report a problem

Back to top