Fast approximation algorithms for computing constrained minimum spanning trees

DOI10.1007/978-3-319-71150-8_9MaRDI QIDQ1699768zbMATH OpenOpenAlexFDO

Authors Pei Yao, Longkun Guo

Publication date 26 February 2018

Full work available at URL https://doi.org/10.1007/978-3-319-71150-8_9

zbMATH Keywords

approximation algorithmbicameral edge replacementconstrained minimum spanning treeFPTAS

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Recommendations

• Exact algorithms for finding constrained minimum spanning trees
• The constrained minimum spanning tree problem
• An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection
• A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
• Polynomial time approximation schemes for the constrained minimum spanning tree problem

Cited in

(7)

• The subdivision-constrained minimum spanning tree problem
• A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
• Exact algorithms for finding constrained minimum spanning trees
• Faster Fully-Dynamic Minimum Spanning Forest
• Polynomial time approximation schemes for the constrained minimum spanning tree problem
• 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: Fast approximation algorithms for computing constrained minimum spanning trees

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