Name
Title | ||
|---|---|---|
The Degree Preserving Spanning Tree Problem: Valid Inequalities and Branch-and-cut method. |
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.endm.2013.05.090 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Degree preserving trees,Vertex feedback edge set,Branch-and-cut | Discrete mathematics,Combinatorics,Minimum degree spanning tree,k-minimum spanning tree,Branch and cut,Integer programming,Connected dominating set,Spanning tree,Shortest-path tree,Mathematics,Minimum spanning tree | Journal |
Volume | ISSN | Citations |
41 | 1571-0653 | 2 |
PageRank | References | Authors |
0.38 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bernard Gendron | 1 | 688 | 49.92 |
| Abilio Lucena | 2 | 362 | 34.05 |
| Alexandre Salles da Cunha | 3 | 242 | 22.32 |
| Luidi Simonetti | 4 | 152 | 15.82 |