Exact algorithms for finding constrained minimum spanning trees

DOI10.1007/s10878-020-00579-zzbMath1502.90185OpenAlexW3023896539MaRDI QIDQ2082219

Pei Yao, Longkun Guo

Publication date: 4 October 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-020-00579-z

zbMATH Keywords

local searchbicameral edge replacementconstrained minimum spanning tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• On the shortest spanning subtree of a graph and the traveling salesman problem
• Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem
• The 2-hop spanning tree problem
• Minimum-weight degree-constrained spanning tree problem: Heuristics and implementation on an SIMD parallel machine
• A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
• Bicriteria Network Design Problems
• An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection
• The constrained minimum spanning tree problem
• Combinatorial optimization. Theory and algorithms.

This page was built for publication: Exact algorithms for finding constrained minimum spanning trees