Show simple item record

dc.contributor.authorHassin, Refael
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.contributor.authorSegev, Danny
dc.date.accessioned2010-01-09T15:02:01Z
dc.date.available2010-01-09T15:02:01Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2848
dc.language.isoenen
dc.subjectHardness of Approximationen
dc.subjectApproximation Algorithmsen
dc.subjectLabeled Connectivityen
dc.subject.ddc003en
dc.titleApproximation algorithms and hardness results for labeled connectivity problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenLet 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.en
dc.relation.isversionofjnlnameJournal of Combinatorial Optimization
dc.relation.isversionofjnlvol14en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate2007-11
dc.relation.isversionofjnlpages437-453en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/s10878-007-9044-xen
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record