The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
주어진 그래프의 연결된 유도 하위 그래프를 열거하는 문제는 고전적이며 잘 연구되었습니다. 연결된 유도 하위 그래프는 각 하위 그래프에 대해 일정한 시간에 열거될 수 있는 것으로 알려져 있습니다. 본 논문에서는 고도로 연결된 유도 하위 그래프에 중점을 둡니다. 그래프에서 연결성의 가장 중요한 개념은 정점 연결성(Vertex Connectivity)입니다. 정점 연결의 경우 다음과 같은 일부 열거 문제 설정 및 열거 알고리즘이 제안되었습니다. k- 꼭지점 연결 스패닝 하위 그래프. 본 논문에서는 그래프 연결성의 또 다른 주요 개념인 에지 연결성에 중점을 둡니다. 이는 도로망에서 대피 경로를 찾는 문제에서 비롯되었습니다. 대피 경로에서는 에지 연결성이 중요합니다. 에지 연결성이 높은 하위 그래프가 두 정점 사이의 여러 경로를 보장하기 때문입니다. 본 논문에서는 주어진 그래프의 2-에지 연결 유도 하위 그래프를 열거하는 문제를 고려합니다. 입력 그래프의 2-에지 연결 유도 하위 그래프를 열거하는 알고리즘을 제시합니다. G 과 n 정점과 m 가장자리. 우리의 알고리즘은 2-에지 연결 유도 하위 그래프를 모두 열거합니다. O(n3m|SG|) 시간, 어디서 SG 는 2-에지 연결 유도 하위 그래프의 집합입니다. G. 또한, 알고리즘을 약간 수정하여 다음과 같은 결과를 얻었습니다. O(n3m)-2-에지 연결 유도 하위 그래프에 대한 지연 열거 알고리즘.
Taishu ITO
Iwate University
Yusuke SANO
Iwate University
Katsuhisa YAMANAKA
Iwate University
Takashi HIRAYAMA
Iwate 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.
부
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
부
@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},}
부
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 -