The subdivision-constrained minimum spanning tree problem

DOI10.1016/J.TCS.2008.12.038MaRDI QIDQ1006063zbMATH OpenOpenAlexFDO

Authors Jianping Li, Weidong Li, Tongquan Zhang, Zhongxu Zhang

Publication date 17 March 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2008.12.038

zbMATH Keywords

polynomial equivalencestrongly polynomial time algorithmsubdivision tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Recommendations

• The constrained minimum spanning tree problem
• A constrained minimum spanning tree problem
• The minimum weight spanning tree with constraints
• Fast approximation algorithms for computing constrained minimum spanning trees
• Exact algorithms for finding constrained minimum spanning trees

Cites work

• A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
• An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection
• Combinatorial Optimization with Rational Objective Functions
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph theory
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Shortest chain subject to side constraints
• The constrained minimum spanning tree problem

Cited in

(6)

• A constrained minimum spanning tree problem
• A unifying model for locally constrained spanning tree problems
• The generalized dependency constrained spanning tree problem
• The subdivision-constrained routing requests problem
• The constrained minimum spanning tree problem
• Extended formulations for the cardinality constrained subtree of a tree problem

This page was built for publication: The subdivision-constrained minimum spanning tree problem

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