论文标题
线性 - 列表枚举，用于最小施纳问题
Linear-Delay Enumeration for Minimal Steiner Problems
论文作者
论文摘要
Kimelfeld和Sagiv [Kimelfeld and Sagiv，Pods 2006]，[Kimelfeld and Sagiv，Inf。系统。 [2008]指出，在数据图上的关键字搜索中，枚举$ k $碎片的问题非常重要。在图理论术语中，该问题对应于（指示）图中的最小施泰纳树。在本文中，我们提出了一种线性延迟和多项式空间算法，用于列举所有最小的施泰纳树，从而改善了[Kimelfeld和Sagiv，Inf的先前结果。系统。 2008]。我们的枚举算法可以扩展到其他Steiner问题，例如最小的Steiner森林，最小的终端Steiner树和最小的定向施罐树。作为最小施泰纳树枚举问题的另一个变体，我们研究了列举最小诱导的施泰纳子图的问题。我们提出了一种在无爪图上最小诱导的施泰纳子图的多项式 - 列表和指数空间枚举算法。与这些可进行的结果相反，我们表明，列举最小的史坦纳树的问题至少与超图上的最小横向枚举问题一样困难。
Kimelfeld and Sagiv [Kimelfeld and Sagiv, PODS 2006], [Kimelfeld and Sagiv, Inf. Syst. 2008] pointed out the problem of enumerating $K$-fragments is of great importance in a keyword search on data graphs. In a graph-theoretic term, the problem corresponds to enumerating minimal Steiner trees in (directed) graphs. In this paper, we propose a linear-delay and polynomial-space algorithm for enumerating all minimal Steiner trees, improving on a previous result in [Kimelfeld and Sagiv, Inf. Syst. 2008]. Our enumeration algorithm can be extended to other Steiner problems, such as minimal Steiner forests, minimal terminal Steiner trees, and minimal directed Steiner trees. As another variant of the minimal Steiner tree enumeration problem, we study the problem of enumerating minimal induced Steiner subgraphs. We propose a polynomial-delay and exponential-space enumeration algorithm of minimal induced Steiner subgraphs on claw-free graphs. Contrary to these tractable results, we show that the problem of enumerating minimal group Steiner trees is at least as hard as the minimal transversal enumeration problem on hypergraphs.
