The complexity of the capacitated tree problem

DOI10.1002/net.3230080306zbMath0443.68048MaRDI QIDQ3886877

Christos H. Papadimitriou

Publication date: 1978

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230080306

zbMATH Keywords

spanning tree; NP-complete; capacitated tree problem; Euclidean capacitated tree problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

94C15: Applications of graph theory to circuits and networks

Related Items

Topological design of telecommunication networks --- local access design methods, Finding minimum cost directed trees with demands and capacities, Dynamic programming based heuristics for the topological design of local access networks, Analysis of heuristics for the design of tree networks, A heuristic approach for capacity expansion of packet networks, Topological design of a centralized communication network with unreliable links and node outage costs, Hybrid fiber co-axial CATV network design with variable capacity optical network units, Multiple center capacitated arc routing problems: A tabu search algorithm using capacitated trees, Heuristic procedure neural networks for the CMST problem, An exact algorithm for the capacitated shortest spanning arborescence, A multiperiod planning model for the capacitated minimal spanning tree problem