The 2-hop spanning tree problem

DOI10.1016/S0167-6377(98)00029-7MaRDI QIDQ1306467zbMATH OpenFDO

Authors Geir Dahl

Publication date 4 October 1999

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10852/9573

zbMATH Keywords

hop-constrained spanning treeinteger programmingpolyhedra

Mathematics Subject Classification ID

Integer programming (90C10)

Recommendations

• The two-level diameter constrained spanning tree problem
• On spanning 2-trees in a graph
• Two dependency constrained spanning tree problems
• The hybrid spanning tree problem
• scientific article; zbMATH DE number 1563034
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• The 2-path network problem
• On the SPANNING k-TREE problem
• scientific article; zbMATH DE number 1305491
• scientific article; zbMATH DE number 1424297

Cites work

• scientific article; zbMATH DE number 3876377 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 795222 (Why is no real title available?)
• Stable Set Polytopes for a Class of Circulant Graphs

Cited in

(14)

• Exact algorithms for finding constrained minimum spanning trees
• Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem
• Minimax flow tree problems
• Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem
• New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints
• The k edge-disjoint 3-hop-constrained paths polytope
• The 2-path network problem
• Network design for time‐constrained delivery
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
• A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem
• Combining integer linear programming with a state‐of‐the‐art heuristic for the 2‐path network design problem
• Restricted dynamic programming based neighborhoods for the hop-constrained minimum spanning tree problem
• New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints
• Approximation algorithms for hop constrained and buy-at-bulk network design via hop constrained oblivious routing

This page was built for publication: The 2-hop spanning tree problem

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