Afficher la notice abrégée

dc.contributor.authorHassin, Refael
dc.contributor.authorMonnot, Jérôme
dc.contributor.authorSegev, Danny
dc.date.accessioned2011-03-22T15:05:25Z
dc.date.available2011-03-22T15:05:25Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5798
dc.language.isoenen
dc.subjects-t pathen
dc.subjects-t cuten
dc.subjectspanning treeen
dc.subjectperfect matchingen
dc.subjecthardness of approximationen
dc.subjectapproximation algorithmsen
dc.subjectBottleneck labeled problemsen
dc.subject.ddc003en
dc.titleThe Complexity of bottleneck labeled graph problemsen
dc.typeCommunication / Conférence
dc.description.abstractenWe present hardness results, approximation heuristics, and exact algorithms for bottleneck labeled optimization problems arising in the context of graph theory. This long-established model partitions the set of edges into classes, each of which is identified by a unique color. The generic objective is to construct a subgraph of prescribed structure (such as that of being an s-t path, a spanning tree, or a perfect matching) while trying to avoid over-picking or under-picking edges from any given color.en
dc.identifier.citationpages328-340en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber4769
dc.relation.ispartoftitleGraph-Theoretic Concepts in Computer Science 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007, Revised Papersen
dc.relation.ispartofeditorBrandstädt, Andreas
dc.relation.ispartofeditorKratsch, Dieter
dc.relation.ispartofeditorMüller, Haiko
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2007
dc.relation.ispartofpages341en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-540-74839-7en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-74838-0en
dc.relation.conftitle33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'07)en
dc.relation.confdate2007-06
dc.relation.confcityDornburgen
dc.relation.confcountryAllemagneen
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-540-74839-7_31


Fichiers attachés à cette notice

Thumbnail

Ce document fait partie de la (des) collection(s) suivante(s)

Afficher la notice abrégée