The Complexity of Bottleneck Labeled Graph Problems

DOI10.1007/978-3-540-74839-7_31zbMath1141.68534MaRDI QIDQ3508579

Jérôme Monnot, Danny Segev, Refael Hassin

Publication date: 1 July 2008

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/5798

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68R10: Graph theory (including graph drawing) in computer science

90C59: Approximation methods and heuristics in mathematical programming

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

The maximum labeled path problem, On two restricted ancestors tree problems, Labeled traveling salesman problems: complexity and approximation

Cites Work

• On approximating the longest path in a graph
• Complexity of the min-max and min-max regret assignment problems
• The labeled perfect matching in bipartite graphs
• Traveling salesman problem under categorization
• Minimum perfect bipartite matchings and spanning trees under categorization
• Robust discrete optimization and its applications
• Multiple criteria optimization: State of the art annotated bibliographic surveys
• On bottleneck assignment problems under categorization.
• Robust discrete optimization and network flows
• The minimum labeling spanning trees
• Matchings in colored bipartite networks
• Local search for the minimum label spanning tree problem with bounded color classes.
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Categorized bottleneck-minisum path problems on networks
• A Bibliography on the Applications of Mathematical Programming Multiple-objective Methods
• Some Matching Problems for Bipartite Graphs
• Maximum matching of given weight in complete and complete bipartite graphs
• Spanning trees with many or few colors in edge-colored graphs
• Multi‐objective combinatorial optimization problems: A survey
• Algorithms – ESA 2005
• Approximation Algorithms and Hardness Results for Labeled Connectivity Problems
• Algorithms and Computation
• Unnamed Item
• Unnamed Item
• Unnamed Item