The complexity of bottleneck labeled graph problems
DOI10.1007/s00453-008-9261-4zbMath1205.68261OpenAlexW2017363428MaRDI QIDQ5961969
Danny Segev, Refael Hassin, Jérôme Monnot
Publication date: 16 September 2010
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://basepub.dauphine.fr/handle/123456789/5798
spanning treeapproximation algorithmsperfect matching\(s\)-\(t\) cut\(s\)-\(t\) pathbottleneck labeled problemshardness of approximation
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
Cites Work
- Unnamed Item
- 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
- Exact arborescences, matchings and cycles
- Matching is as easy as matrix inversion
- 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.
- A survey and annotated bibliography of multiobjective combinatorial optimization
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Categorized bottleneck-minisum path problems on networks
- Approximation algorithms and hardness results for labeled connectivity problems
- A Bibliography on the Applications of Mathematical Programming Multiple-objective Methods
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Two-Commodity Flow
- Spanning trees with many or few colors in edge-colored graphs
- Multi‐objective combinatorial optimization problems: A survey
- Algorithms – ESA 2005
- Algorithms and Computation
