Comparison of algorithms for the degree constrained minimum spanning tree

DOI10.1023/A:1011977126230zbMath0987.68613OpenAlexW1948148225MaRDI QIDQ5960737

Mohan Krishnamoorthy, Andreas T. Ernst, Yazid M. Sharaiha

Publication date: 2001

Published in: Journal of Heuristics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1011977126230

zbMATH Keywords

heuristicsdegree constrainted minimum spanning treetree representation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (16)

The generalized dependency constrained spanning tree problem ⋮ Remarks on the application of genetic algorithm and tabu search method to nonlinear spanning tree problems ⋮ ILP formulation of the degree-constrained minimum spanning hierarchy problem ⋮ Variable neighborhood search for the degree-constrained minimum spanning tree problem ⋮ Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations ⋮ Novel degree constrained minimum spanning tree algorithm based on an improved multicolony ant algorithm ⋮ Degree-constrained \(k\)-minimum spanning tree problem ⋮ Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem ⋮ LS(graph): a constraint-based local search for constraint optimization on trees and paths ⋮ A computational study on the maximum-weight bounded-degree rooted tree problem ⋮ New genetic algorithm approach for the MIN-degree constrained minimum spanning tree ⋮ Using Lagrangian dual information to generate degree constrained spanning trees ⋮ DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH ⋮ Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints ⋮ A unifying model for locally constrained spanning tree problems ⋮ VNS and second order heuristics for the min-degree constrained minimum spanning tree problem

This page was built for publication: Comparison of algorithms for the degree constrained minimum spanning tree