IEICE TRANSACTIONS on Information
A Polynomial Delay Algorithm for Enumerating 2-Edge-Connected Induced Subgraphs
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(n3m|SG|) time, where SG is the set of the 2-edge-connected induced subgraphs of G. Moreover, by slightly modifying the algorithm, we have a O(n3m)-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
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
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(n3m|SG|) time, where SG is the set of the 2-edge-connected induced subgraphs of G. Moreover, by slightly modifying the algorithm, we have a O(n3m)-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(n3m|SG|) time, where SG is the set of the 2-edge-connected induced subgraphs of G. Moreover, by slightly modifying the algorithm, we have a O(n3m)-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(n3m|SG|) time, where SG is the set of the 2-edge-connected induced subgraphs of G. Moreover, by slightly modifying the algorithm, we have a O(n3m)-delay enumeration algorithm for 2-edge-connected induced subgraphs.
ER -
English
