A Linear Delay Algorithm for Enumeration of 2-Edge/Vertex-connected Induced Subgraphs
For a set system (V,šā 2^V), we call a subset Cāš a component. A nonempty subset Yā C is a minimal removable set (MRS) of C if Cā Yāš and no proper nonempty subset Zā Y satisfies Cā Zāš. In this paper, we consider the problem of enumerating all components in a set system such that, for every two components C,C'āš with C'ā C, every MRS X of C satisfies either Xā C' or Xā© C'=ā . We provide a partition-based algorithm for this problem, which yields the first linear delay algorithms to enumerate all 2-edge-connected induced subgraphs, and to enumerate all 2-vertex-connected induced subgraphs.
READ FULL TEXT