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
TypeCommunication / Conférence
Conference title33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'07)
Book titleGraph-Theoretic Concepts in Computer Science 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007, Revised Papers
Book authorBrandstädt, Andreas; Kratsch, Dieter; Müller, Haiko
Series titleLecture Notes in Computer Science
Number of pages341
MetadataShow full item record
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 / Keywordss-t path; s-t cut; spanning tree; perfect matching; hardness of approximation; approximation algorithms; Bottleneck labeled problems
Showing items related by title and author.