2026-07-25T06:29:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11499 2024-03-06T10:48:09Z ddc:004 open_access

A Polynomial-Delay Algorithm for Enumerating Connectors Under Various Connectivity Conditions Haraguchi, Kazuya Nagamochi, Hiroshi Graph with itemsets Enumeration Polynomial-delay algorithms Connectors We are given an instance (G,I,sigma) with a graph G=(V,E), a set I of items, and a function sigma:V -> 2^I. For a subset X of V, let G[X] denote the subgraph induced from G by X, and I_sigma(X) denote the common item set over X. A subset X of V such that G[X] is connected is called a connector if, for any vertex v in V\X, G[X cup {v}] is not connected or I_sigma(X cup {v}) is a proper subset of I_sigma(X). In this paper, we present the first polynomial-delay algorithm for enumerating all connectors. For this, we first extend the problem of enumerating connectors to a general setting so that the connectivity condition on X in G can be specified in a more flexible way. We next design a new algorithm for enumerating all solutions in the general setting, which leads to a polynomial-delay algorithm for enumerating all connectors for several connectivity conditions on X in G, such as the biconnectivity of G[X] or the k-edge-connectivity among vertices in X in G. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kazuya Haraguchi and Hiroshi Nagamochi 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.3 urn:nbn:de:0030-drops-114990 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.3 eng https://creativecommons.org/licenses/by/3.0/legalcode