Spanning cactus: complexity and extensions

DOI10.1016/j.dam.2017.08.020zbMath1372.05218OpenAlexW2756538301MaRDI QIDQ2410246

Chinmay Debnath, Alak Kumar Datta

Publication date: 17 October 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2017.08.020

zbMATH Keywords

NP-completenessminimum spanning treeapproximation algorithmsminimum spanning cactus

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• The minimum spanning tree problem with conflict constraints and its variations
• Two-edge connected spanning subgraphs and polyhedra
• An optimal algorithm for solving the 1-median problem on weighted 4-cactus graphs
• Spanning cactus of a graph: Existence, extension, optimization, and approximation
• Complexity of the directed spanning cactus problem
• The connectivity carcass of a vertex subset in a graph and its incremental maintenance
• Centdian Computation in Cactus Graphs
• An analysis of alternative strategies for implementing matching algorithms
• Sensitivity analysis of optimal matchings
• Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time

This page was built for publication: Spanning cactus: complexity and extensions