A space optimal algorithm for the enumeration of maximal double idependent subsets of a graph


Ladislav Novak, Žarko Karadžić, Dragan M. Acketa




A space optimal algorithm is introduced for generating all the maximal simultaneously circuitless and cutsetless edge-subsets of a 2-connected graph $G$. The algorithm makes use of three Boolean functions, which test whether a candidate for such a maximal double independent set is valid. The efficiency of the tests is due to the fact that they use local search only; one need not produce the families of all the circuits and cutsets of $G$.