Approximation Algorithms and Hardness Results for Labeled Connectivity Problems

DOI10.1007/11821069_42MaRDI QIDQ5756701zbMATH OpenOpenAlexFDO

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

Publication date 5 September 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11821069_42

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Connectivity (05C40)

Recommendations

• Approximation algorithms and hardness results for labeled connectivity problems
• Algorithmic and hardness results for the hub labeling problem
• Approximation and Hardness Results for Label Cut and Related Problems
• Approximation and hardness results for label cut and related problems
• Approximation algorithms for connectivity augmentation problems
• Approximating subset \(k\)-connectivity problems
• Approximating subset \(k\)-connectivity problems
• Approximation algorithms for approximating graphs with bounded number of connected components
• scientific article; zbMATH DE number 1947057
• Hardness of Approximation for Vertex-Connectivity Network Design Problems

Cited in

(3)

• A note on the minimum label spanning tree.
• The Complexity of Bottleneck Labeled Graph Problems
• Approximation algorithms and hardness results for labeled connectivity problems

This page was built for publication: Approximation Algorithms and Hardness Results for Labeled Connectivity Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5756701)