A Linear Time Algorithm for the Minimum Spanning Caterpillar Problem for Bounded Treewidth Graphs

DOI10.1007/978-3-642-13284-1_19MaRDI QIDQ3569129zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

optimizationtreewidthnetworks topologyspanning caterpillars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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

Cited in

(6)

• Euclidean networks with a backbone and a limit theorem for minimum spanning caterpillars
• On the minimum caterpillar problem in digraphs
• Facet-inducing inequalities with acyclic supports for the caterpillar-packing polytope
• The caterpillar-packing polytope
• Upper and lower bounding procedures for the minimum caterpillar spanning problem
• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs

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)