Approximation algorithms and hardness results for labeled connectivity problems

被引：0
作者：
Refael Hassin
Jérôme Monnot
Danny Segev
机构：
[1] Tel-Aviv University,School of Mathematical Sciences
[2] CNRS LAMSADE,undefined
[3] Université Paris-Dauphine,undefined
来源：
Journal of Combinatorial Optimization | 2007年 / 14卷
关键词：
Labeled connectivity; Approximation algorithms; Hardness of approximation;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Let G=(V,E) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function ℒ:E→ℕ. In addition, each label ℓ∈ℕ has a non-negative cost c(ℓ). The minimum label spanning tree problem (MinLST) asks to find a spanning tree in G that minimizes the overall cost of the labels used by its edges. Equivalently, we aim at finding a minimum cost subset of labels I⊆ℕ such that the edge set {e∈E:ℒ(e)∈I} forms a connected subgraph spanning all vertices. Similarly, in the minimum label s–t path problem (MinLP) the goal is to identify an s–t path minimizing the combined cost of its labels. The main contributions of this paper are improved approximation algorithms and hardness results for MinLST and MinLP.
引用
收藏
页码：437 / 453
页数：16
相关论文
共 48 条
[1]  
Ageev AA(2004)Pipage rounding: a new method of constructing algorithms with proven performance guarantee J Comb Optim 8 307-328
[2]  
Sviridenko M(1995)When trees collide: an approximation algorithm for the generalized Steiner problem on networks SIAM J Comput 24 440-456
[3]  
Agrawal A(2003)Improved low-degree testing and its applications Combinatorica 23 365-426
[4]  
Klein PN(2005)Approximating MIN 2-SAT and MIN 3-SAT Theory Comput Syst 38 329-345
[5]  
Ravi R(1997)Spanning trees with many or few colors in edge-colored graphs Discuss Math Graph Theory 17 259-269
[6]  
Arora S(2005)Paths and cycles in colored graphs Australas J Comb 31 299-311
[7]  
Sudan M(2003)Local search for the minimum label spanning tree problem with bounded color classes Oper Res Lett 31 195-201
[8]  
Avidor A(1997)The minimum labeling spanning trees Inf Process Lett 63 277-282
[9]  
Zwick U(2005)On the hardness of approximating minimum vertex cover Ann Math 162 439-486
[10]  
Broersma H(1995)A general approximation technique for constrained forest problems SIAM J Comput 24 296-317
12345