Modeling and solving the angular constrained minimum spanning tree problem

DOI10.1016/J.COR.2019.104775MaRDI QIDQ2329732zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 18 October 2019

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2019.104775

zbMATH Keywords

angular constrained spanning treesbranch-and-cut algorithmscombinatorial optimizationpolyhedral combinatorics

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem
• Bounded-angle spanning tree: modeling networks with angular constraints
• Bounded-angle spanning tree: modeling networks with angular constraints
• Bounded-angle minimum spanning trees
• A 4-approximation of the \(\frac{ 2 \pi}{ 3} \)-MST

Cites work

• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Benchmarking optimization software with performance profiles.
• Bounded-angle spanning tree: modeling networks with angular constraints
• Connectivity guarantees for wireless networks with directional antennas
• Ice-creams and wedge graphs
• Introduction to algorithms.
• Matroids and the greedy algorithm
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Trees and Cuts
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(7)

• A 75 angle constraint for plane minimal T1 trees
• A unifying model for locally constrained spanning tree problems
• Bounded-angle minimum spanning trees
• A 4-approximation of the \(\frac{ 2 \pi}{ 3} \)-MST
• Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem
• Bounded-angle spanning tree: modeling networks with angular constraints
• Bounded-angle spanning tree: modeling networks with angular constraints

Describes a project that uses

Uses Software

• TSPLIB
• XPRESS

This page was built for publication: Modeling and solving the angular constrained minimum spanning tree problem

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