Degree-constrained k-minimum spanning tree problem

DOI10.1155/2020/7628105zbMATHOpenAlexMaRDI QIDQ2221985FDO

Authors Pablo Adasme, Ali Dehghan Firoozabadi

Publication date 3 February 2021

Published in Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1155/2020/7628105

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27)

Recommendations

• 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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Lagrangean approach to the degree-constrained minimum spanning tree problem
• 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
• 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
• 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

Cited in

(5)

• Edge exchanges in the degree-constrained minimum spanning tree problem
• Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
• Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming
• DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH
• Models and heuristics for the \(k\)-degree constrained minimum spanning tree problem with node-degree costs

Describes a project that uses

Uses Software

• CPLEX
• GitHub

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)