• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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
2007
Journal name
Journal of Combinatorial Optimization
Volume
14
Number
4
Publisher
Springer
Pages
437-453
Publication identifier
http://dx.doi.org/10.1007/s10878-007-9044-x
Metadata
Show full item record
Author(s)
Hassin, Refael
Monnot, Jérôme cc
Segev, Danny
Abstract (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 Connectivity

Related items

Showing items related by title and author.

  • Thumbnail
    Approximation Algorithms and Hardness Results for Labeled Connectivity Problems 
    Hassin, Refael; Monnot, Jérôme; Segev, Danny (2006) Communication / Conférence
  • Thumbnail
    The Complexity of bottleneck labeled graph problems 
    Hassin, Refael; Monnot, Jérôme; Segev, Danny (2007) Communication / Conférence
  • Thumbnail
    Approximation algorithms for some vehicle routing problems 
    Bazgan, Cristina; Monnot, Jérôme; Hassin, Refael (2005) Article accepté pour publication ou publié
  • Thumbnail
    Differential approximation for some routing problems 
    Bazgan, Cristina; Hassin, Refael; Monnot, Jérôme (2003) Communication / Conférence
  • Thumbnail
    A note on the hardness results for the labeled perfect matching problems in bipartite graphs 
    Monnot, Jérôme (2008) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo