Complexity of spanning tree problems: Part I

DOI10.1016/0377-2217(80)90164-2zbMath0445.90088OpenAlexW2072970829MaRDI QIDQ1145635

Paolo M. Camerini, Francesco Maffioli, Giulia Galbiati

Publication date: 1980

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(80)90164-2

zbMATH Keywords

network designcomplexity of spanning tree problemsoptimum weighted trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25)

Related Items

Computing a \((1+\varepsilon)\)-approximate geometric minimum-diameter spanning tree, Most and least uniform spanning trees, Spanning trees with minimum weighted degrees, 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, A uniform self-stabilizing minimum diameter spanning tree algorithm, Heuristics and their design: A survey, Graphical-structure-based models for routing problems, On the complexity of finding multi-constrained spanning trees, Topological design of telecommunication networks --- local access design methods, Combinatorial network abstraction by trees and distances, Complexity of independency and cliquy trees, A unifying model for locally constrained spanning tree problems, In memoriam Paolo M. Camerini, The Bounded Path Tree Problem, The matroidal knapsack: A class of (often) well-solvable problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• The Min-Max Spanning Tree Problem and some extensions
• The complexity of the capacitated tree problem
• Computing capacitated minimal spanning trees efficiently
• On the Computational Complexity of Combinatorial Problems
• Finding Minimum Spanning Trees
• The complexity of the network design problem