The subdivision-constrained minimum spanning tree problem

DOI10.1016/j.tcs.2008.12.038zbMath1168.90588OpenAlexW2090523464MaRDI QIDQ1006063

Tongquan Zhang, Weidong Li, Zhongxu Zhang, Jianping Li

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

subdivision treepolynomial equivalencestrongly polynomial time algorithm

Mathematics Subject Classification ID

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

Related Items (1)

The subdivision-constrained routing requests problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Shortest chain subject to side constraints
• Combinatorial Optimization with Rational Objective Functions
• 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: The subdivision-constrained minimum spanning tree problem