Nothing Special   »   [go: up one dir, main page]

IEICE Transactions on Information and Systems
Online ISSN : 1745-1361
Print ISSN : 0916-8532
Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm
A Polynomial Delay Algorithm for Enumerating 2-Edge-Connected Induced Subgraphs
Taishu ITOYusuke SANOKatsuhisa YAMANAKATakashi HIRAYAMA
Author information
JOURNAL FREE ACCESS

2022 Volume E105.D Issue 3 Pages 466-473

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

Content from these authors
© 2022 The Institute of Electronics, Information and Communication Engineers
Previous article Next article
feedback
Top