On \(k\)-connectivity problems with sharpened triangle inequality
From MaRDI portal
Publication:1002105
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
combinatorial problemsgraph algorithmsapproximation algorithmsminimum-cost \(k\)-connected spanning subgraph
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
