Complexity of the directed spanning cactus problem

DOI10.1016/j.dam.2004.08.006zbMath1087.90081OpenAlexW1998313956MaRDI QIDQ1765377

Anna Palbom

Publication date: 23 February 2005

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

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

zbMATH Keywords

ComplexityNP-completeAsymmetric TSPDirected cactiSpanning cacti

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items

The shortest connection game, Spanning cactus: complexity and extensions, Quasi-Transitive Digraphs and Their Extensions, Approximate spanning cactus

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Remarks on Hamiltonian properties of powers of digraphs
• On the approximability of the traveling salesman problem (extended abstract)
• Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• P-Complete Approximation Problems
• Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time