Complexity of finding a join of maximum weight
Complexity of finding a join of maximum weight
复制标题
查找最大权重连接的复杂性
DOI：
10.1016/s0166-218x(00)00355-3
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
A. Ageev
中科院分区：
文献类型：
--
作者：
A. Ageev
无向图G的边子集J ∈ E（G）称为联，如果G的每个圈的边至多有一半包含在J中.本文考虑求最大权联的问题：给定图G和边权c：E（G）→ R，求最大权联.我们证明了即使在0，1-权的情况下，该问题也是NP-难的，这回答了一个问题A。弗兰克不同意。我们还证明了在串-平行图和任意权的情况下，问题可以在O（n3）的时间内解决，其中n是G中的顶点数。
A subset of edges J⊆E(G) in a undirected graph G is called a join if at most half the edges of each cycle of G are contained in J. In this paper we consider the problem of finding a join of maximum weight: given a graph G and an edge weighting c : E(G)→ R , find a join of maximum weight. We show that the problem is NP-hard even in the case of 0,1-weights, which answers a question of A. Frank in the negative. We also show that in the case of series–parallel graphs and arbitrary weights, the problem can be solved in time O(n3), where n is the number of vertices in G.