The complexity of bottleneck labeled graph problems
DOI10.1007/S00453-008-9261-4zbMATH Open1205.68261OpenAlexW2017363428MaRDI QIDQ5961969FDOQ5961969
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
Recommendations
approximation algorithmsperfect matchinghardness of approximationspanning tree\(s\)-\(t\) cut\(s\)-\(t\) pathbottleneck labeled problems
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Cites Work
- Title not available (Why is that?)
- Multiple criteria optimization: State of the art annotated bibliographic surveys
- Robust discrete optimization and its applications
- Robust discrete optimization and network flows
- Title not available (Why is that?)
- Title not available (Why is that?)
- On approximating the longest path in a graph
- A survey and annotated bibliography of multiobjective combinatorial optimization
- The labeled perfect matching in bipartite graphs
- Spanning trees with many or few colors in edge-colored graphs
- Matching is as easy as matrix inversion
- A Bibliography on the Applications of Mathematical Programming Multiple-objective Methods
- Multi‐objective combinatorial optimization problems: A survey
- The minimum labeling spanning trees
- Approximation algorithms and hardness results for labeled connectivity problems
- Complexity of the min-max and min-max regret assignment problems
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Traveling salesman problem under categorization
- Exact arborescences, matchings and cycles
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Algorithms and Computation
- Title not available (Why is that?)
- Local search for the minimum label spanning tree problem with bounded color classes.
- Minimum perfect bipartite matchings and spanning trees under categorization
- Algorithms – ESA 2005
- Matchings in colored bipartite networks
- Two-Commodity Flow
- Categorized bottleneck-minisum path problems on networks
- On bottleneck assignment problems under categorization.
Cited In (2)
This page was built for publication: The complexity of bottleneck labeled graph problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5961969)
