Premium
Formulations and exact solution approaches for the degree preserving spanning tree problem
Author(s) -
da Cunha Alexandre Salles,
Simonetti Luidi,
Lucena Abilio,
Gendron Bernard
Publication year - 2015
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21590
Subject(s) - spanning tree , degree (music) , minimum spanning tree , mathematical optimization , tree (set theory) , mathematics , computer science , minimum degree spanning tree , distributed minimum spanning tree , combinatorics , physics , acoustics
Given a connected and undirected graph G , the degree preserving spanning tree problem (DPSTP) asks for a spanning tree of G with the maximum number of vertices having the same degree in the tree and in G . These are called full degree vertices. We introduce integer programming formulations, valid inequalities and four exact solution approaches based on different formulations. Two branch‐and‐bound procedures, a branch‐and‐cut (BC) algorithm and an iterative probing combinatorial Benders decomposition method are introduced here. The problem of optimally lifting one of the classes of valid inequalities proposed here is equivalent to solving a DPSTP instance, for a conveniently defined subgraph of G . We thus apply one of the proposed methods to optimally lift these cuts, within the other solution methods. In doing so, two additional algorithms, a hybrid Benders decomposition and a hybrid BC are proposed. Extensive computational experiments are conducted with the solution algorithms introduced in this study. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(4), 329–343 2015