Lower and upper bounds for the spanning tree with minimum branch vertices

DOI10.1007/s10589-013-9556-5zbMath1312.90038MaRDI QIDQ377727

Francesco Carrabs, Manlio Gaudioso, Monica Gentili, Raffaele Cerulli

Publication date: 7 November 2013

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10589-013-9556-5

zbMATH Keywords

Lagrangian relaxation; spanning tree; dual ascent

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C05: Trees

90C10: Integer programming

90C56: Derivative-free methods and methods using generalized derivatives

Related Items

Exact and heuristic approaches for the maximum lifetime problem in sensor networks with coverage and connectivity constraints, Spanning Trees with Few Branch Vertices, OMEGA one multi ethnic genetic approach, Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem, A branch-and-cut algorithm for the minimum branch vertices spanning tree problem, Truck synchronization at single door cross-docking terminals, An exact algorithm to extend lifetime through roles allocation in sensor networks with connectivity constraints, Decomposition methods based on articulation vertices for degree-dependent spanning tree problems, An exact and heuristic approach for the \(d\)-minimum branch vertices problem, Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem, The generalized minimum branch vertices problem: properties and polyhedral analysis, Scatter search for the minimum leaf spanning tree problem, Relations, models and a memetic approach for three degree-dependent spanning tree problems, Approximating spanning trees with few branches, An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices, An edge-swap heuristic for generating spanning trees with minimum number of branch vertices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints
• Bounded-degree spanning tree problems: models and new algorithms
• Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints
• On solving the Lagrangian dual of integer programs via an incremental approach
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
• Spanning trees with many or few colors in edge-colored graphs
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• An Incremental Method for Solving Convex Finite Min-Max Problems