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
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)
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