On the complexity of finding multi-constrained spanning trees

DOI10.1016/0166-218X(83)90014-8zbMath0498.90078MaRDI QIDQ1171508

Paolo M. Camerini, Giulia Galbiati, Francesco Maffioli

Publication date: 1983

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

zbMATH Keywords

computational complexityclassification of undirected spanning tree problemsmulti-constrained, unweighted caseundirected, unweighted graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35)

Related Items (15)

An overview of graph covering and partitioning ⋮ Spanning trees with minimum weighted degrees ⋮ A new approach for the multiobjective minimum spanning tree ⋮ Heuristics with Constant Error Guarantees for the Multi Center Capacitated Minimum Spanning Tree Problem ⋮ On some multicriteria arborescence problems: Complexity and algorithms ⋮ On the approximability of some maximum spanning tree problems ⋮ On the approximability of some Maximum Spanning Tree Problems ⋮ Social distancing network creation ⋮ Topological design of telecommunication networks --- local access design methods ⋮ The image of weighted combinatorial problems ⋮ Kruskal with embedded C-semirings to solve MST problems with partially-ordered costs ⋮ A unifying model for locally constrained spanning tree problems ⋮ In memoriam Paolo M. Camerini ⋮ Unnamed Item ⋮ A successful algorithm for the undirected Hamiltonian path problem

Cites Work

• Unnamed Item
• Complexity of spanning tree problems: Part I
• The Bounded Path Tree Problem

This page was built for publication: On the complexity of finding multi-constrained spanning trees