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

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (3)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: The Complexity of Bottleneck Labeled Graph Problems