Approximation algorithms and hardness results for labeled connectivity problems
Hassin, Refael; Monnot, Jérôme; Segev, Danny (2007), Approximation algorithms and hardness results for labeled connectivity problems, Journal of Combinatorial Optimization, 14, 4, p. 437-453. http://dx.doi.org/10.1007/s10878-007-9044-x
Type
Article accepté pour publication ou publiéDate
2007Journal name
Journal of Combinatorial OptimizationVolume
14Number
4Publisher
Springer
Pages
437-453
Publication identifier
Metadata
Show full item recordAbstract (EN)
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.Subjects / Keywords
Hardness of Approximation; Approximation Algorithms; Labeled ConnectivityRelated items
Showing items related by title and author.
-
Hassin, Refael; Monnot, Jérôme; Segev, Danny (2006) Communication / Conférence
-
Hassin, Refael; Monnot, Jérôme; Segev, Danny (2007) Communication / Conférence
-
Bazgan, Cristina; Monnot, Jérôme; Hassin, Refael (2005) Article accepté pour publication ou publié
-
Bazgan, Cristina; Hassin, Refael; Monnot, Jérôme (2003) Communication / Conférence
-
Monnot, Jérôme (2008) Article accepté pour publication ou publié