The complexity of the capacitated tree problem

DOI10.1002/net.3230080306zbMath0405.68043OpenAlexW1972674272MaRDI QIDQ4191605

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

Computational ComplexityNp-CompletenessComputer NetworksEfficiency of AlgorithmsCapacitated Tree ProblemSharma-El Bardai Algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Theory of software (68N99)

Related Items

A biased random-key genetic algorithm for the capacitated minimum spanning tree problem ⋮ Survivable network design: the capacitated minimum spanning network problem ⋮ How easy is local search? ⋮ A voltage drop limited decentralized electric power distribution network ⋮ On the complexity of graph tree partition problems. ⋮ On the edge capacitated Steiner tree problem ⋮ Heuristics for the multi-level capacitated minimum spanning tree problem ⋮ Characterizing acyclic graphs by labeling edges ⋮ Design of capacitated degree constrained min-sum arborescence