Approximate spanning cactus

DOI10.1016/j.ipl.2015.06.009zbMath1331.68291OpenAlexW929930557MaRDI QIDQ2353648

Alak Kumar Datta

Publication date: 15 July 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2015.06.009

zbMATH Keywords

NP-completenessminimum spanning treeapproximation algorithmsspanning cactus\(\tau\)-triangle inequality

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Performance guarantees for the TSP with a parameterized triangle inequality
• 1-Approximation algorithm for bottleneck disjoint path matching
• The Min-Max Spanning Tree Problem and some extensions
• Spanning cactus of a graph: Existence, extension, optimization, and approximation
• Complexity of the directed spanning cactus problem
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• The connectivity carcass of a vertex subset in a graph and its incremental maintenance
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time

This page was built for publication: Approximate spanning cactus