On a Network Design Problem That Is Intractable on Trees

DOI10.1287/MOOR.15.3.530MaRDI QIDQ3486349zbMATH OpenOpenAlexFDO

Authors Daniel Bienstock, Odile Marcotte

Publication date 1990

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/moor.15.3.530

zbMATH Keywords

approximation algorithmcoveringnetwork designNP-hardpackingpath bundling

Mathematics Subject Classification ID

Paths and cycles (05C38) Network design and communication in computer systems (68M10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Communication networks in operations research (90B18) Programming involving graphs or networks (90C35) Dynamic programming (90C39) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• The 2-path network problem
• The path set packing problem
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Path-matching problems
• The problems of selecting an optimal path on network

Cited in

(8)

• Complexity and approximability of minimum path-collection exact covers
• Interdicting facilities in tree networks
• Bundling all shortest paths
• scientific article; zbMATH DE number 2161745 (Why is no real title available?)
• scientific article; zbMATH DE number 1834661 (Why is no real title available?)
• scientific article; zbMATH DE number 6297807 (Why is no real title available?)
• Tree embeddings for hop-constrained network design
• The path-variance problem on tree networks

This page was built for publication: On a Network Design Problem That Is Intractable on Trees

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