Lower and upper bounds for the spanning tree with minimum branch vertices
From MaRDI portal
Publication:377727
DOI10.1007/s10589-013-9556-5zbMath1312.90038OpenAlexW2022130029MaRDI 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
Programming involving graphs or networks (90C35) Trees (05C05) Integer programming (90C10) Derivative-free methods and methods using generalized derivatives (90C56)
Related Items (20)
An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices ⋮ Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem ⋮ Scatter search for the minimum leaf 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 ⋮ Maximum weighted induced forests and trees: new formulations and a computational comparative review ⋮ A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs ⋮ Decomposition methods based on articulation vertices for degree-dependent spanning tree problems ⋮ Spanning trees with few branch vertices in graphs of bounded neighborhood diversity ⋮ A genetic approach for the 2‐edge‐connected minimum branch vertices problem ⋮ Exact and heuristic approaches for the maximum lifetime problem in sensor networks with coverage and connectivity constraints ⋮ An edge-swap heuristic for generating spanning trees with minimum number of branch vertices ⋮ An exact and heuristic approach for the \(d\)-minimum branch vertices problem ⋮ Relations, models and a memetic approach for three degree-dependent spanning tree problems ⋮ 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 ⋮ OMEGA one multi ethnic genetic approach ⋮ Spanning Trees with Few Branch Vertices ⋮ Approximating spanning trees with few branches
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
This page was built for publication: Lower and upper bounds for the spanning tree with minimum branch vertices
