A Linear Delay Algorithm of Enumerating Strongly-Connected Induced Subgraphs Based on SSD Set System
摘要
In this paper, we propose a linear delay algorithm that enumerates all strongly-connected induced subgraphs of a given digraph. We consider the problem in a general framework based on what we call Superset-Subset-Disjoint (SSD) set system. Introducing basic properties of this novel set system, we show that, given a graph, the family of vertex subsets that induce k-edge-connected subgraphs is an SSD system. We then develop an algorithm that enumerates all subsets in an SSD system and show that the delay is linear with respect to the ground set size and the running time of three oracles that implicitly describe the SSD system. Finally, for the purpose of enumerating all strongly-connected induced subgraphs, we present linear-time implementation of the three oracles.