Approximate spanning cactus

DOI10.1016/J.IPL.2015.06.009MaRDI QIDQ2353648zbMATH OpenOpenAlexFDO

Authors 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

\(\tau\)-triangle inequalityapproximation algorithmsminimum spanning treeNP-completenessspanning cactus

Mathematics Subject Classification ID

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

Recommendations

• Spanning cactus: complexity and extensions
• Spanning cactus of a graph: Existence, extension, optimization, and approximation
• Complexity of the directed spanning cactus problem
• The constrained minimum spanning tree problem
• Algorithms and Computation

Cites work

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

Cited in

(3)

• The degree resistance distance of cacti
• Spanning cactus: complexity and extensions
• Spanning cactus and spanning cactus extension of outerplanar graphs

This page was built for publication: Approximate spanning cactus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2353648)