Thumbnail

The Complexity of bottleneck labeled graph problems

Hassin, Refael; Monnot, Jérôme; Segev, Danny (2007), The Complexity of bottleneck labeled graph problems, in Brandstädt, Andreas; Kratsch, Dieter; Müller, Haiko, Graph-Theoretic Concepts in Computer Science 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007, Revised Papers, Springer : Berlin, p. 328-340. http://dx.doi.org/10.1007/978-3-540-74839-7_31

View/Open
Type
Communication / Conférence
Date
2007
Conference title
33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'07)
Conference date
2007-06
Conference city
Dornburg
Conference country
Allemagne
Book title
Graph-Theoretic Concepts in Computer Science 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007, Revised Papers
Book author
Brandstädt, Andreas; Kratsch, Dieter; Müller, Haiko
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
4769
Published in
Berlin
ISBN
978-3-540-74838-0
Number of pages
341
Pages
328-340
Publication identifier
Metadata
Show full item record
Author(s)
Hassin, Refael
Monnot, Jérôme cc
Segev, Danny
Abstract (EN)
We 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.
Subjects / Keywords
s-t path; s-t cut; spanning tree; perfect matching; hardness of approximation; approximation algorithms; Bottleneck labeled problems