Formulations and exact solution approaches for the degree preserving spanning tree problem. Issue 4 (11th March 2015)

• Record Type: Journal Article
• Authors: da Cunha, Alexandre Salles; Simonetti, Luidi; Lucena, Abilio; Gendron, Bernard
• Is Part Of: Networks. Volume 65:Issue 4(2015:Jul.)
• Page Start: 329
• Page End: 343
• Publication Date: 2015-03-11
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21590
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main"> <title> <x xml:space="preserve">Abstract</x> </title> <p>Given a connected and undirected graph <italic>G</italic>, the degree preserving spanning tree problem (DPSTP) asks for a spanning tree of <italic>G</italic> with the maximum number of vertices having the same degree in the tree and in <italic>G</italic>. 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 <italic>G</italic>. 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</p> </abstract>