A Polynomial Delay Algorithm for Enumerating 2-Edge-Connected Induced Subgraphs

Taishu ITO; Yusuke SANO; Katsuhisa YAMANAKA; Takashi HIRAYAMA

doi:10.1587/transinf.2021FCP0005

A Polynomial Delay Algorithm for Enumerating 2-Edge-Connected Induced Subgraphs

Taishu ITO, Yusuke SANO, Katsuhisa YAMANAKA, Takashi HIRAYAMA

Full Text Views

0

Cite this

Summary :

The problem of enumerating connected induced subgraphs of a given graph is classical and studied well. It is known that connected induced subgraphs can be enumerated in constant time for each subgraph. In this paper, we focus on highly connected induced subgraphs. The most major concept of connectivity on graphs is vertex connectivity. For vertex connectivity, some enumeration problem settings and enumeration algorithms have been proposed, such as k-vertex connected spanning subgraphs. In this paper, we focus on another major concept of graph connectivity, edge-connectivity. This is motivated by the problem of finding evacuation routes in road networks. In evacuation routes, edge-connectivity is important, since highly edge-connected subgraphs ensure multiple routes between two vertices. In this paper, we consider the problem of enumerating 2-edge-connected induced subgraphs of a given graph. We present an algorithm that enumerates 2-edge-connected induced subgraphs of an input graph G with n vertices and m edges. Our algorithm enumerates all the 2-edge-connected induced subgraphs in O(n³m|S_G|) time, where S_G is the set of the 2-edge-connected induced subgraphs of G. Moreover, by slightly modifying the algorithm, we have a O(n³m)-delay enumeration algorithm for 2-edge-connected induced subgraphs.

Publication: IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.466-473

Publication Date: 2022/03/01

Publicized: 2021/07/02

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2021FCP0005

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -)

Category

Authors

Taishu ITO
  Iwate University
Yusuke SANO
  Iwate University
Katsuhisa YAMANAKA
  Iwate University
Takashi HIRAYAMA
  Iwate University

Keyword

enumeration algorithm, 2-edge-connected induced subgraph, reverse search, polynomial delay

Cite this

Copy

Taishu ITO, Yusuke SANO, Katsuhisa YAMANAKA, Takashi HIRAYAMA, "A Polynomial Delay Algorithm for Enumerating 2-Edge-Connected Induced Subgraphs" in IEICE TRANSACTIONS on Information, vol. E105-D, no. 3, pp. 466-473, March 2022, doi: 10.1587/transinf.2021FCP0005.
Abstract: The problem of enumerating connected induced subgraphs of a given graph is classical and studied well. It is known that connected induced subgraphs can be enumerated in constant time for each subgraph. In this paper, we focus on highly connected induced subgraphs. The most major concept of connectivity on graphs is vertex connectivity. For vertex connectivity, some enumeration problem settings and enumeration algorithms have been proposed, such as k-vertex connected spanning subgraphs. In this paper, we focus on another major concept of graph connectivity, edge-connectivity. This is motivated by the problem of finding evacuation routes in road networks. In evacuation routes, edge-connectivity is important, since highly edge-connected subgraphs ensure multiple routes between two vertices. In this paper, we consider the problem of enumerating 2-edge-connected induced subgraphs of a given graph. We present an algorithm that enumerates 2-edge-connected induced subgraphs of an input graph G with n vertices and m edges. Our algorithm enumerates all the 2-edge-connected induced subgraphs in O(n³m|S_G|) time, where S_G is the set of the 2-edge-connected induced subgraphs of G. Moreover, by slightly modifying the algorithm, we have a O(n³m)-delay enumeration algorithm for 2-edge-connected induced subgraphs.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021FCP0005/_p

Copy

@ARTICLE{e105-d_3_466,
author={Taishu ITO, Yusuke SANO, Katsuhisa YAMANAKA, Takashi HIRAYAMA, },
journal={IEICE TRANSACTIONS on Information},
title={A Polynomial Delay Algorithm for Enumerating 2-Edge-Connected Induced Subgraphs},
year={2022},
volume={E105-D},
number={3},
pages={466-473},
abstract={The problem of enumerating connected induced subgraphs of a given graph is classical and studied well. It is known that connected induced subgraphs can be enumerated in constant time for each subgraph. In this paper, we focus on highly connected induced subgraphs. The most major concept of connectivity on graphs is vertex connectivity. For vertex connectivity, some enumeration problem settings and enumeration algorithms have been proposed, such as k-vertex connected spanning subgraphs. In this paper, we focus on another major concept of graph connectivity, edge-connectivity. This is motivated by the problem of finding evacuation routes in road networks. In evacuation routes, edge-connectivity is important, since highly edge-connected subgraphs ensure multiple routes between two vertices. In this paper, we consider the problem of enumerating 2-edge-connected induced subgraphs of a given graph. We present an algorithm that enumerates 2-edge-connected induced subgraphs of an input graph G with n vertices and m edges. Our algorithm enumerates all the 2-edge-connected induced subgraphs in O(n³m|S_G|) time, where S_G is the set of the 2-edge-connected induced subgraphs of G. Moreover, by slightly modifying the algorithm, we have a O(n³m)-delay enumeration algorithm for 2-edge-connected induced subgraphs.},
keywords={},
doi={10.1587/transinf.2021FCP0005},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - A Polynomial Delay Algorithm for Enumerating 2-Edge-Connected Induced Subgraphs
T2 - IEICE TRANSACTIONS on Information
SP - 466
EP - 473
AU - Taishu ITO
AU - Yusuke SANO
AU - Katsuhisa YAMANAKA
AU - Takashi HIRAYAMA
PY - 2022
DO - 10.1587/transinf.2021FCP0005
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2022
AB - The problem of enumerating connected induced subgraphs of a given graph is classical and studied well. It is known that connected induced subgraphs can be enumerated in constant time for each subgraph. In this paper, we focus on highly connected induced subgraphs. The most major concept of connectivity on graphs is vertex connectivity. For vertex connectivity, some enumeration problem settings and enumeration algorithms have been proposed, such as k-vertex connected spanning subgraphs. In this paper, we focus on another major concept of graph connectivity, edge-connectivity. This is motivated by the problem of finding evacuation routes in road networks. In evacuation routes, edge-connectivity is important, since highly edge-connected subgraphs ensure multiple routes between two vertices. In this paper, we consider the problem of enumerating 2-edge-connected induced subgraphs of a given graph. We present an algorithm that enumerates 2-edge-connected induced subgraphs of an input graph G with n vertices and m edges. Our algorithm enumerates all the 2-edge-connected induced subgraphs in O(n³m|S_G|) time, where S_G is the set of the 2-edge-connected induced subgraphs of G. Moreover, by slightly modifying the algorithm, we have a O(n³m)-delay enumeration algorithm for 2-edge-connected induced subgraphs.
ER -