A Linear Delay Algorithm for Enumeration of 2-Edge/Vertex-connected Induced Subgraphs

02/10/2023
āˆ™
by   Takumi Tada, et al.
āˆ™
0
āˆ™

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

Please sign up or login with your details

Forgot password? Click here to reset