On the complexity of the one-terminal network design problem

DOI10.1016/0167-6377(82)90007-4MaRDI QIDQ1169929zbMATH OpenOpenAlexFDO

Authors Nimrod Megiddo

Publication date 1982

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(82)90007-4

zbMATH Keywords

computational complexityminimum spanning treenetwork topologyNP-hardnessoptimal solutionconstruction costsone terminal network designproportional to distance travel costsusage costs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the computational power of pushdown automata
• The One-Terminal TELPAK Problem

This page was built for publication: On the complexity of the one-terminal network design problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1169929)