Complexity of the directed spanning cactus problem
type: Item
instance of: scholarly article
title: Complexity of the directed spanning cactus problem
zbMATH Open document ID: 1087.90081
author: Anna Palbom
published in: Discrete Applied Mathematics
publication date: 2005-02-23T00:00:00Z
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 2137379
zbMATH Keywords: Directed cacti
zbMATH Keywords: Spanning cacti
zbMATH Keywords: Complexity
zbMATH Keywords: NP-complete
zbMATH Keywords: Asymmetric TSP
MaRDI profile type: Publication
full work available at URL: j.dam.2004.08.006
OpenAlex ID: W1998313956
cites work: Introduction to algorithms
cites work: Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
cites work: On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
cites work: Q4198056
cites work: Q5187226
cites work: Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs
cites work: Q4142699
cites work: On the approximability of the traveling salesman problem (extended abstract)
cites work: P-Complete Approximation Problems
cites work: Remarks on Hamiltonian properties of powers of digraphs
DOI: 10.1016/J.DAM.2004.08.006
Recommended article: Parameterized complexity of directed spanner problems
Recommended article: Parameterized Complexity of Directed Spanner Problems.
Recommended article: Spanning cactus: complexity and extensions
Recommended article: On the directed full degree spanning tree problem
Recommended article: Q4474221
Recommended article: Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
Recommended article: On the Directed Degree-Preserving Spanning Tree Problem
Recommended article: The complexity of the locally connected spanning tree problem
Recommended article: NP-completeness and degree restricted spanning trees
description: scientific article; zbMATH DE number 2137379