A Linear Time Algorithm for the Minimum Spanning Caterpillar Problem for Bounded Treewidth Graphs
DOI10.1007/978-3-642-13284-1_19zbMATH Open1284.68455OpenAlexW1516348081MaRDI QIDQ3569129FDOQ3569129
Authors: Michael J. Dinneen, Masoud Khosravani 
Publication date: 17 June 2010
Published in: Structural Information and Communication Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-13284-1_19
Recommendations
- A randomized linear-time algorithm for finding minimum spanning trees (extended abstract)
- Upper and lower bounding procedures for the minimum caterpillar spanning problem
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- A randomized linear-time algorithm to find minimum spanning trees
- A linear-time algorithm for finding a minimum spanning pseudoforest
- Near-linear time algorithm for approximate minimum degree spanning trees
- An algorithm for geometric minimum spanning trees requiring nearly linear expected time
- An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees
- A branch and bound algorithm for the capacitated minimum spanning tree problem
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cited In (6)
- Facet-inducing inequalities with acyclic supports for the caterpillar-packing polytope
- Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
- The caterpillar-packing polytope
- On the minimum caterpillar problem in digraphs
- Upper and lower bounding procedures for the minimum caterpillar spanning problem
- Euclidean networks with a backbone and a limit theorem for minimum spanning caterpillars
This page was built for publication: A Linear Time Algorithm for the Minimum Spanning Caterpillar Problem for Bounded Treewidth Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569129)
