Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs
Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs
复制标题
DOI：
10.4230/lipics.mfcs.2019.73
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
A. Conte;R. Grossi;M. Kanté;Andrea Marino;T. Uno;Kunihiro Wasa
中科院分区：
文献类型：
--
作者：
A. Conte;R. Grossi;M. Kanté;Andrea Marino;T. Uno;Kunihiro Wasa
本文将诱发的施泰纳子图作为经典坦Steiner树的一种变体，以使（指数级的许多）施泰纳树共享相同的基础诱导子绘图。如果未固定端子的数量，则比众所周知的超透明横向枚举问题要困难。多项式延迟算法列出了所有诱导的施泰纳子图最小尺寸。
This paper investigates induced Steiner subgraphs as a variant of the classical Steiner trees, so as to compactly represent the (exponentially many) Steiner trees sharing the same underlying induced subgraph. We prove that the enumeration of all (inclusion-minimal) induced Steiner subgraphs is harder than the well-known Hypergraph Transversal enumeration problem if the number of terminals is not fixed. When the number of terminals is fixed, we propose a polynomial delay algorithm for listing all induced Steiner subgraphs of minimum size. We also propose a polynomial delay algorithm for listing the set of minimal induced Steiner subgraphs when the number of terminals is 3