md-MST is NP-hard for

DOI10.1016/j.endm.2010.05.002zbMath1237.90270OpenAlexW1545167657MaRDI QIDQ2883542

Pedro Martins, Maurício C. Souza, Ana de Almeida

Publication date: 13 May 2012

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2010.05.002

zbMATH Keywords

computational complexityspanning treenode degree constraintsproof by reduction

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

A strong symmetric formulation for the min-degree constrained minimum spanning tree problem ⋮ A hybrid steady-state genetic algorithm for the min-degree constrained minimum spanning tree problem ⋮ The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm ⋮ New genetic algorithm approach for the MIN-degree constrained minimum spanning tree ⋮ A unifying model for locally constrained spanning tree problems ⋮ When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• Transitions in geometric minimum spanning trees
• A greedy heuristic for a minimum-weight forest problem
• Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
• On two geometric problems related to the travelling salesman problem

This page was built for publication: md-MST is NP-hard for