首页    期刊浏览 2024年11月08日 星期五
登录注册

文章基本信息

  • 标题:A Polynomial-Delay Algorithm for Enumerating Connectors Under Various Connectivity Conditions
  • 本地全文:下载
  • 作者:Kazuya Haraguchi ; Hiroshi Nagamochi
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2019
  • 卷号:149
  • 页码:1-15
  • DOI:10.4230/LIPIcs.ISAAC.2019.3
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:Graph with itemsets; Enumeration; Polynomial-delay algorithms; Connectors
国家哲学社会科学文献中心版权所有