Linear-Delay Enumeration for Minimal Steiner Problems
Linear-Delay Enumeration for Minimal Steiner Problems
复制标题
最小 Steiner 问题的线性延迟枚举
DOI：
10.1145/3517804.3524148
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Wasa Kunihiro
中科院分区：
文献类型：
--
作者：
Kobayashi Yasuaki;Kurita Kazuhiro;Wasa Kunihiro
Kimelfeld和Sagiv [Kimelfeld和Sagiv，PODS 2006]，[Kimelfeld和Sagiv，Inf.Syst.2008]指出，枚举K片段的问题在数据图上的关键字搜索中非常重要。在图论术语中，该问题对应于在（有向）图中枚举最小Steiner树。在本文中，我们提出了一个线性延迟和多项式空间算法枚举所有的最小Steiner树，改进以前的结果[Kimelfeld和Sagiv，Inf.Syst.2008]。我们的枚举算法可以扩展到其他Steiner问题，如最小Steiner森林，最小终端Steiner树，最小定向Steiner树。作为最小Steiner树计数问题的另一个变体，我们研究了最小导出Steiner子图的计数问题。提出了无爪图上最小导出Steiner子图的多项式延迟指数空间计数算法。相反，这些易于处理的结果，我们表明，问题的枚举最小组Steiner树至少是硬的超图的最小横向枚举问题。
Kimelfeld and Sagiv [Kimelfeld and Sagiv, PODS 2006], [Kimelfeld and Sagiv, Inf. Syst. 2008] pointed out that 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.
登录
查看更多内容
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
影响因子：
1.1
作者：
L. Khachiyan;E. Boros;K. Borys;Khaled M. Elbassioni;V. Gurvich;K. Makino
通讯作者：
K. Makino
DOI：
10.1016/s0166-218x(00)00339-5
发表时间：
2002
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
B. Schwikowski;Ewald Speckenmeyer
通讯作者：
Ewald Speckenmeyer
均匀方向度量中的 Steiner 最小树
DOI：
10.1007/978-1-4613-0255-1_1
发表时间：
2001
期刊：
--
影响因子：
--
作者：
M. Brazil
通讯作者：
M. Brazil
关于拟阵的一些枚举问题的复杂性
DOI：
--
发表时间：
2006
期刊：
SIAM Journal on Discrete Mathematics 19
影响因子：
--
作者：
L.Khachiyan;E.Boros;K.Elbassioni;V.Gurvich;K.Makino
通讯作者：
K.Makino