Polynomial time approximation schemes for the constrained minimum spanning tree problem

DOI10.1155/2012/394721zbMath1251.90373OpenAlexW1977567299WikidataQ58906823 ScholiaQ58906823MaRDI QIDQ442910

Yen Hung Chen

Publication date: 6 August 2012

Published in: Journal of Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1155/2012/394721

zbMATH Keywords

minimum spanning tree problempolynomial time approximation schemes

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Risk-control approach for a bottleneck spanning tree problem with the total network reliability under uncertainty

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of quality of service routing
• A PTAS for weight constrained Steiner trees in series--parallel graphs.
• A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
• An improved FPTAS for Restricted Shortest Path.
• Shortest chain subject to side constraints
• Approximation Schemes for the Restricted Shortest Path Problem
• Bicriteria Network Design Problems
• Approximating Capacitated Routing and Delivery Problems
• An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection
• Routing to Multiple Destinations in Computer Networks
• A simple efficient approximation scheme for the restricted shortest path problem