Polynomial time approximation schemes for the constrained minimum spanning tree problem

DOI10.1155/2012/394721zbMATH Open1251.90373OpenAlexW1977567299WikidataQ58906823 ScholiaQ58906823MaRDI QIDQ442910FDOQ442910

Authors: 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

Recommendations

• An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection
• The constrained minimum spanning tree problem
• Fast approximation algorithms for computing constrained minimum spanning trees
• Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
• Spanning trees with minimum weighted degrees

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)

Cites Work

• Introduction to algorithms
• A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
• An improved FPTAS for Restricted Shortest Path.
• Approximation Schemes for the Restricted Shortest Path Problem
• A simple efficient approximation scheme for the restricted shortest path problem
• Title not available (Why is that?)
• An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection
• Routing to Multiple Destinations in Computer Networks
• On the complexity of quality of service routing
• Title not available (Why is that?)
• Shortest chain subject to side constraints
• Approximating Capacitated Routing and Delivery Problems
• A PTAS for weight constrained Steiner trees in series--parallel graphs.
• \(k\)-pair delay constrained minimum cost routing in undirected networks

Cited In (10)

• Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
• A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
• A polynomial time approximation scheme for the two-source minimum routing cost spanning trees
• Risk-control approach for a bottleneck spanning tree problem with the total network reliability under uncertainty
• Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• Fast approximation algorithms for computing constrained minimum spanning trees
• The Minimum Spanning Tree Problem with Time Window Constraints
• An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection
• The constrained minimum spanning tree problem

This page was built for publication: Polynomial time approximation schemes for the constrained minimum spanning tree problem

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