Mixed-integer programming approaches for the tree t^*-spanner problem

DOI10.1007/S11590-018-1340-0MaRDI QIDQ2329685zbMATH OpenOpenAlexFDO

Authors Eduardo Álvarez-Miranda, Markus Sinnl

Publication date 18 October 2019

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-018-1340-0

zbMATH Keywords

Benders decompositionbranch-and-cutgraph spannerstree \(t^*\)-spanner problem

Mathematics Subject Classification ID

Mixed integer programming (90C11) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• The tree-star problem: a formulation and a branch-and-cut algorithm
• Tree Spanners
• Solving diameter-constrained minimum spanning tree problems by constraint programming
• Isomorphic tree spanner problems
• A new formulation for spanning trees

Cites work

• A dual ascent approach for steiner tree problems on a directed graph
• A survey on Benders decomposition applied to fixed-charge network design problems
• Additive graph spanners
• An Optimal Synchronizer for the Hypercube
• Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
• Complexity of network synchronization
• Computing Visibility Information in an Inaccurate Simple Polygon
• scientific article; zbMATH DE number 795222 (Why is no real title available?)
• Lower-Stretch Spanning Trees
• On implementing push-relabel method for the maximum flow problem
• On sparse spanners of weighted graphs
• Reconstructing the shape of a tree from observed dissimilarity data
• Restrictions of minimum spanner problems
• Routing to Multiple Destinations in Computer Networks
• Solving Steiner tree problems in graphs to optimality
• Tailoring Benders decomposition for uncapacitated network design
• Thinning out Steiner trees: a node-based model for uniform edge costs
• Tree Spanners

Cited in

(7)

• Graph spanners: a tutorial review
• Exact approaches for the minimum subgraph diameter problem
• The tree-star problem: a formulation and a branch-and-cut algorithm
• General variable neighborhood search for the minimum stretch spanning tree problem
• Tree 3-spanners on generalized prisms of graphs
• Polynomial algorithms for sparse spanners on subcubic graphs
• Iterated local search with two strategies in the acceptance criterion for the tree t-spanner problem

Describes a project that uses

Uses Software

• SteinLib

This page was built for publication: Mixed-integer programming approaches for the tree \(t^*\)-spanner problem

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