On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality

DOI10.1016/j.tcs.2004.06.019zbMath1093.68070OpenAlexW2153849284MaRDI QIDQ703542

Dirk Bongartz, Walter Unger, Hans-Joachim Böckenhauer, Ralf Klasing, Sebastian Seibert, Juraj Hromkovič, Guido Proietti

Publication date: 11 January 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.06.019

zbMATH Keywords

Approximation algorithmGraph augmentationInapproximabilityMinimum-cost biconnected spanning subgraph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (7)

On the approximability of the single allocation \(p\)-hub center problem with parameterized triangle inequality ⋮ Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality ⋮ Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem ⋮ A Modern View on Stability of Approximation ⋮ Approximating survivable networks with \(\beta \)-metric costs ⋮ Approximation algorithms for the \(p\)-hub center routing problem in parameterized metric graphs ⋮ On \(k\)-connectivity problems with sharpened triangle inequality

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Performance guarantees for the TSP with a parameterized triangle inequality
• Approximation algorithms for the TSP with sharpened triangle inequality
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• Geometric algorithms and combinatorial optimization
• Polynomial time algorithms for 2-edge-connectivity augmentation problems
• An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• NOTE Improved Approximation Algorithms for Weighted 2- and 3-Vertex Connectivity Augmentation Problems
• Approximation Algorithms for Graph Augmentation
• Augmentation Problems
• A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph Problem
• Biconnectivity approximations and graph carvings
• Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• A Staged Primal-Dual Algorithm for Perfect b-Matching with Edge Capacities

This page was built for publication: On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality