On Finding Acyclic Subhypergraphs
On Finding Acyclic Subhypergraphs
复制标题
关于寻找无环子超图
DOI：
10.1007/11537311_43
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
M. Harao
中科院分区：
文献类型：
--
作者：
Kouichi Hirata;M. Kuwabara;M. Harao
本文研究了在超图中寻找非循环子超图的问题。首先，我们证明了判定一个超图是否有泛连通无圈子超图的问题是NP-完全的。本文还证明了对于给定的K> 0，判定一个超图是否有至少包含Khyperedgesis的无圈子超图的问题是NP-完全的。接着，我们引入了极大无环子超图，它是一个无环子超图，如果我们把原超图的任何一个超边加到它上面，它就是循环的，然后我们设计了一个线性时间算法来寻找它，该算法是基于Tarjan和Yannakakis（1984）设计的无环性检验算法。
In this paper, we investigate the problem of findingacyclicsubhypergraphs in a hypergraph. First we show that the problem of determining whether or not a hypergraph has aspanning connected acyclic subhypergraphis NP-complete. Also we show that, for a givenK> 0, the problem of determining whether or not a hypergraph hasan acyclic subhypergraph containing at least Khyperedgesis NP-complete. Next, we introduce amaximalacyclic subhypergraph, which is an acyclic subhypergraph that is cyclic if we add any hyperedge of the original hypergraph to it. Then, we design the linear-time algorithmmasto find it, which is based on theacyclicity test algorithmdesigned by Tarjan and Yannakakis (1984).