Back
Journal article Scopus Source The journal / series is indexed in Scopus (SCImago list). The article itself has not been verified. 28 Citations Quartil Q1

Min-degree constrained minimum spanning tree problem: Complexity, properties, and formulations

de Almeida, A.M. , Martins, P. , de Souza, M.C.
ISLA — Instituto Politécnico de Gestão e Tecnologia
International Transactions in Operational Research, Volume 19, Issue 3, 2012, pp. 323–352
DOI: 10.1111/j.1475-3995.2011.00830.x

Resume

Abstract
AbstractThis paper addresses a new combinatorial problem, the Min‐Degree Constrained Minimum Spanning Tree (md‐MST), that can be stated as: given a weighted undirected graph with positive costs on the edges and a node‐degrees function , the md‐MST is to find a minimum cost spanning tree T of G, where each node i of T either has at least a degree of or is a leaf node. This problem is closely related to the well‐known Degree Constrained Minimum Spanning Tree (d‐MST) problem, where the degree constraint is an upper bound instead.The general NP‐hardness for the md‐MST is established and some properties related to the feasibility of the solutions for this problem are presented, in particular we prove some bounds on the number of internal and leaf nodes. Flow‐based formulations are proposed and computational experiments involving the associated Linear Programming (LP) relaxations are presented.

Keywords

#degree-constrained minimum spanning tree #NP-hardness #leaf nodes #flow-based formulation #linear programming relaxation #combinatorial optimization #weighted undirected graphs #Combinatorics #Degree (music) #Mathematics #Spanning tree #Minimum spanning tree #Node (physics) #Tree (set theory) #Graph

Bibliographic Details

Publication Type Journal article
Publication Year 2012
Journal / Conference / Work International Transactions in Operational Research
Volume / Issue Vol. 19 (3)
Pagination pp. 323–352
Quartile (SCImago) Q1
Scopus Indexing Indexed source (via SCImago)

ISLA Authors & Affiliations

P
Pedro João Coimbra Martins
pmartins@iscac.pt ID: 1113-BC3A-435F
Profile