Complexity of spanning tree problems: Part I

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

Giulia Galbiati, Francesco Maffioli, Paolo M. Camerini

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 design; complexity of spanning tree problems; optimum weighted trees

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

Related Items

The Bounded Path Tree Problem, The matroidal knapsack: A class of (often) well-solvable problems, Combinatorial network abstraction by trees and distances, Most and least uniform spanning trees, Heuristics and their design: A survey, On the complexity of finding multi-constrained spanning trees, Topological design of telecommunication networks --- local access design methods, On the approximability of some Maximum Spanning Tree Problems, In memoriam Paolo M. Camerini, Computing a \((1+\varepsilon)\)-approximate geometric minimum-diameter spanning tree, On some multicriteria arborescence problems: Complexity and algorithms, Graphical-structure-based models for routing problems, Heuristics with Constant Error Guarantees for the Multi Center Capacitated Minimum Spanning Tree Problem

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item