The Degree Preserving Spanning Tree Problem: Valid Inequalities and Branch-and-cut method |
| |
| Affiliation: | 1. University of Ottawa, Ottawa, Ontario, Canada;2. Federal University of Minas Gerais, Belo Horizonte, MG, Brazil;3. Federal University of Para, Belem, PA, Brazil |
| |
| Abstract: | Given a connected undirected graph G, the Degree Preserving Spanning Tree Problem (DPSTP) consists in finding a spanning tree T of G that maximizes the number of vertices that have the same degree in T and in G. In this paper, we introduce Integer Programming formulations, valid inequalities and a Branch-and-cut algorithm for the DPSTP. Reinforced with new valid inequalities, the upper bounds provided by the formulation behind our Branch-and-cut method dominate previous DPSTP bounds in the literature. |
| |
| Keywords: | Degree preserving trees Vertex feedback edge set Branch-and-cut |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
