Generating Cut Conjunctions in Graphs and Related Problems
Generating Cut Conjunctions in Graphs and Related Problems
复制标题
生成图中的割连词及相关问题
DOI：
10.1007/s00453-007-9111-9
复制
发表时间：
2008
期刊：
影响因子：
1.1
通讯作者：
K. Makino
中科院分区：
文献类型：
--
作者：
L. Khachiyan;E. Boros;K. Borys;Khaled M. Elbassioni;V. Gurvich;K. Makino
摘要
设G=（V，E）是一个无向图，B ∈ V×V是一个顶点对的集合.本文给出了一个生成所有极小边集X <$E的多项式时间增量算法，使得每对（s，t）∈B的顶点在（V，E <$X）中不连通，推广了已知的生成所有极小s-t割的有效算法.我们还提出了一个生成所有极小子集X <$E的增量多项式时间算法，使得没有（s，t）∈B是（V，X <$B）中的桥。上述两个问题都是一个更一般的问题的特殊情况，我们称之为生成拟阵的割合取：给定一个在基集S=E <$B上的拟阵M，生成所有的极小子集X <$E，使得没有元素b∈B被E <$X张成。与上述特殊情况不同，对应于图（V，E B）的圈和上圈拟阵，更一般的向量拟阵的割合取问题是NP-困难的。
Abstract
Let G=(V,E) be an undirected graph, and let B⊆V×V be a collection of vertex pairs. We give an incremental polynomial time algorithm to generate all minimal edge sets X⊆E such that every pair (s,t)∈B of vertices is disconnected in (V,E∖X), generalizing well-known efficient algorithms for generating all minimal s-t cuts, for a given pair s,t of vertices. We also present an incremental polynomial time algorithm for generating all minimal subsets X⊆E such that no (s,t)∈B is a bridge in (V,X∪B). Both above problems are special cases of a more general problem that we call generating cut conjunctions for matroids: given a matroid M on ground set S=E∪B, generate all minimal subsets X⊆E such that no element b∈B is spanned by E∖X. Unlike the above special cases, corresponding to the cycle and cocycle matroids of the graph (V,E∪B), the more general problem of generating cut conjunctions for vectorial matroids turns out to be NP-hard.
关于拟阵的一些枚举问题的复杂性
DOI：
--
发表时间：
2006
期刊：
SIAM Journal on Discrete Mathematics 19
影响因子：
--
作者：
L.Khachiyan;E.Boros;K.Elbassioni;V.Gurvich;K.Makino
通讯作者：
K.Makino