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

DOI10.1007/978-3-642-13284-1_19zbMath1284.68455OpenAlexW1516348081MaRDI QIDQ3569129

Masoud Khosravani, Michael J. Dinneen

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)

Related Items (2)

The caterpillar-packing polytope ⋮ Facet-inducing inequalities with acyclic supports for the caterpillar-packing polytope

This page was built for publication: A Linear Time Algorithm for the Minimum Spanning Caterpillar Problem for Bounded Treewidth Graphs