Edge exchanges in the degree-constrained minimum spanning tree problem
From MaRDI portal
We describe a branch and bound algorithm to solve the degree-constrained minimum spanning tree problem. We propose an edge exchange analysis frequently used in the algorithm and three types of heuristic methods. Computational results are reported for problems with up to 200 vertices. These results are much better than known results from the literature.
Recommendations
- Degree-constrained \(k\)-minimum spanning tree problem
- Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem
- Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
- A multiperiod degree constrained minimal spanning tree problem
- Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
- DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH
- The most vital edges in the minimum spanning tree problem
- Approximating minimum-cost graph problems with spanning tree edges
- Lower and upper bounds for the degree-constrained minimum spanning tree problem
- The constrained minimum spanning tree problem
Cites work
- A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
- A note on two problems in connexion with graphs
- Edge exchanges in the degree-constrained minimum spanning tree problem
- scientific article; zbMATH DE number 3225808 (Why is no real title available?)
- The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
- The traveling-salesman problem and minimum spanning trees: Part II
- Topological design of centralized computer networks—formulations and algorithms
Cited in
(25)- A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs
- Edge exchanges in the degree-constrained minimum spanning tree problem
- A Lagrangean approach to the degree-constrained minimum spanning tree problem
- Variable neighborhood search for the degree-constrained minimum spanning tree problem
- Finding extremal carcasses with preset vertex degrees by the replacement method
- Design of a degree-constrained minimal spanning tree with unreliable links and node outage costs.
- Lagrangian and branch-and-cut approaches for upgrading spanning tree problems
- Novel degree constrained minimum spanning tree algorithm based on an improved multicolony ant algorithm
- A hybrid steady-state genetic algorithm for the min-degree constrained minimum spanning tree problem
- Heuristic methods and applications: A categorized survey
- A multiperiod degree constrained minimal spanning tree problem
- Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
- Design of capacitated degree constrained min-sum arborescence
- An exact algorithm for multi-constrained minimum spanning tree problem
- Using Lagrangian dual information to generate degree constrained spanning trees
- A branch and cut method for the degree-constrained minimum spanning tree problem
- Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
- scientific article; zbMATH DE number 1054929 (Why is no real title available?)
- Models and heuristics for the \(k\)-degree constrained minimum spanning tree problem with node-degree costs
- The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm
- Network design for time‐constrained delivery
- Branch and cut methods for network optimization
- Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints
- Non delayed relax-and-cut algorithms
- Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem
This page was built for publication: Edge exchanges in the degree-constrained minimum spanning tree problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1086497)
