Degree-constrained k-minimum spanning tree problem
Summary: Let \(G(V,E)\) be a simple undirected complete graph with vertex and edge sets \(V\) and \(E\), respectively. In this paper, we consider the degree-constrained \(k\)-minimum spanning tree (DC \(k\) MST) problem which consists of finding a minimum cost subtree of \(G\) formed with at least \(k\) vertices of \(V\) where the degree of each vertex is less than or equal to an integer value \(d\leq k-2\). In particular, in this paper, we consider degree values of \(d\in\{ 2,3\}\). Notice that DC \(k\) MST generalizes both the classical degree-constrained and \(k\)-minimum spanning tree problems simultaneously. In particular, when \(d=2\), it reduces to a \(k\)-Hamiltonian path problem. Application domains where DC \(k\) MST can be adapted or directly utilized include backbone network structures in telecommunications, facility location, and transportation networks, to name a few. It is easy to see from the literature that the DC \(k\) MST problem has not been studied in depth so far. Thus, our main contributions in this paper can be highlighted as follows. We propose three mixed-integer linear programming (MILP) models for the DC \(k\) MST problem and derive for each one an equivalent counterpart by using the handshaking lemma. Then, we further propose ant colony optimization (ACO) and variable neighborhood search (VNS) algorithms. Each proposed ACO and VNS method is also compared with another variant of it which is obtained while embedding a Q-learning strategy. We also propose a pure Q-learning algorithm that is competitive with the ACO ones. Finally, we conduct substantial numerical experiments using benchmark input graph instances from TSPLIB and randomly generated ones with uniform and Euclidean distance costs with up to 400 nodes. Our numerical results indicate that the proposed models and algorithms allow obtaining optimal and near-optimal solutions, respectively. Moreover, we report better solutions than CPLEX for the large-size instances. Ultimately, the empirical evidence shows that the proposed Q-learning strategies can bring considerable improvements.
- Models and heuristics for the \(k\)-degree constrained minimum spanning tree problem with node-degree costs
- Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem
- Comparison of algorithms for the degree constrained minimum spanning tree
- Novel degree constrained minimum spanning tree algorithm based on an improved multicolony ant algorithm
- DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH
- A branch and cut method for the degree-constrained minimum spanning tree problem
- A hybrid steady-state genetic algorithm for the min-degree constrained minimum spanning tree problem
- A Lagrangean approach to the degree-constrained minimum spanning tree problem
- Comparison of algorithms for the degree constrained minimum spanning tree
- Cooperative Control of Multiple Agents With Unknown High-Frequency Gain Signs Under Unbalanced and Switching Topologies
- Exact solution approaches for the multi-period degree constrained minimum spanning tree problem
- Facility location with tree topology and radial distance constraints
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
- Integer programming for urban design
- Introduction to algorithms.
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Saving an epsilon: a 2-approximation for the k-MST problem in graphs
- Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem
- Spanning Trees—Short or Small
- Stochastic maximum weight forest problem
- The Steiner tree problem on graphs: inapproximability results
- Using Lagrangian dual information to generate degree constrained spanning trees
- Variable neighborhood search
- Variable neighborhood search: Principles and applications
- Edge exchanges in the degree-constrained minimum spanning tree problem
- Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming
- DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH
- Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
- Models and heuristics for the \(k\)-degree constrained minimum spanning tree problem with node-degree costs
This page was built for publication: Degree-constrained \(k\)-minimum spanning tree problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2221985)
