Approximation Algorithms and Hardness Results for Labeled Connectivity Problems

DOI10.1007/11821069_42zbMATH Open1132.68820OpenAlexW1909158042MaRDI QIDQ5756701FDOQ5756701

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

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

Mathematics Subject Classification ID

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

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)