The complexity of bottleneck labeled graph problems

DOI10.1007/S00453-008-9261-4MaRDI QIDQ5961969zbMATH OpenOpenAlexFDO

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

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

zbMATH Keywords

approximation algorithmsperfect matchinghardness of approximationspanning tree\(s\)-\(t\) cut\(s\)-\(t\) pathbottleneck labeled problems

Mathematics Subject Classification ID

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)

Recommendations

• The Complexity of Bottleneck Labeled Graph Problems
• Algorithms and Computation
• The labeled perfect matching in bipartite graphs
• Algorithms for two bottleneck optimization problems
• On the minimum label spanning tree problem

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2147947 (Why is no real title available?)
• scientific article; zbMATH DE number 3390827 (Why is no real title available?)
• A Bibliography on the Applications of Mathematical Programming Multiple-objective Methods
• A survey and annotated bibliography of multiobjective combinatorial optimization
• Algorithms and Computation
• Algorithms – ESA 2005
• Approximation algorithms and hardness results for labeled connectivity problems
• Categorized bottleneck-minisum path problems on networks
• Complexity of the min-max and min-max regret assignment problems
• Exact arborescences, matchings and cycles
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Local search for the minimum label spanning tree problem with bounded color classes.
• Matching is as easy as matrix inversion
• Matchings in colored bipartite networks
• Minimum perfect bipartite matchings and spanning trees under categorization
• Multiple criteria optimization: State of the art annotated bibliographic surveys
• Multi‐objective combinatorial optimization problems: A survey
• On approximating the longest path in a graph
• On bottleneck assignment problems under categorization.
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Robust discrete optimization and its applications
• Robust discrete optimization and network flows
• Spanning trees with many or few colors in edge-colored graphs
• The labeled perfect matching in bipartite graphs
• The minimum labeling spanning trees
• Traveling salesman problem under categorization
• Two-Commodity Flow

Cited in

(4)

• The labeled perfect matching in bipartite graphs
• The Complexity of Bottleneck Labeled Graph Problems
• Algorithms and Computation
• Algorithms and complexity for a class of combinatorial optimization problems with labelling

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)