On \(k\)-connectivity problems with sharpened triangle inequality

DOI10.1016/j.jda.2008.03.003zbMath1154.90576OpenAlexW2057017626MaRDI QIDQ1002105

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

Publication date: 23 February 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2008.03.003

zbMATH Keywords

combinatorial problemsgraph algorithmsapproximation algorithmsminimum-cost \(k\)-connected spanning subgraph

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

On the Complexity of the Star p-hub Center Problem with Parameterized Triangle Inequality, 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

Cites Work

• 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 hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
• Approximating node connectivity problems via set covers
• Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• Handbook of Approximation Algorithms and Metaheuristics
• A Better Approximation Ratio for the Minimum Sizek-Edge-Connected Spanning Subgraph Problem
• Biconnectivity approximations and graph carvings
• An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
• A 2-Approximation Algorithm for Finding an Optimum 3-Vertex-Connected Spanning Subgraph
• A 3-Approximation Algorithm for Finding Optimum 4,5-Vertex-Connected Spanning Subgraphs
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• Improved Approximation Algorithms for Uniform Connectivity Problems
• Approximating k-node Connected Subgraphs via Critical Graphs
• THE MAXIMUM CONNECTIVITY OF A GRAPH