Name
Title | ||
|---|---|---|
Decomposition methods based on articulation vertices for degree-dependent spanning tree problems. |
Abstract | ||
|---|---|---|
Decomposition methods for optimal spanning trees on graphs are explored in this work. The attention is focused on optimization problems where the objective function depends only on the degrees of the nodes of the tree. In particular, we deal with the Minimum Leaves problem, the Minimum Branch Vertices problem and the Minimum Degree Sum problem. The decomposition is carried out by identifying the articulation vertices of the graph and then its blocks, solving certain subproblems on the blocks and then bringing together the optimal sub-solutions following adequate procedures. Computational results obtained using similar Integer Programming formulations for both the original and the decomposed problems show the advantage of the proposed methods on decomposable graphs. |
Year | DOI | Venue |
|---|---|---|
2017 | https://doi.org/10.1007/s10589-017-9924-7 | Comp. Opt. and Appl. |
Keywords | Field | DocType |
Integer Programming,Spanning tree,Articulation vertex,Block-cutpoint graph | Discrete mathematics,Combinatorics,Trémaux tree,Mathematical optimization,Minimum degree spanning tree,Distributed minimum spanning tree,k-minimum spanning tree,Euclidean minimum spanning tree,Spanning tree,Shortest-path tree,Mathematics,Minimum spanning tree | Journal |
Volume | Issue | ISSN |
68 | 3 | 0926-6003 |
Citations | PageRank | References |
2 | 0.38 | 14 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mercedes Landete | 1 | 150 | 12.88 |
| Alfredo Marín | 2 | 453 | 32.98 |
| José L. Sainz-Pardo | 3 | 2 | 0.38 |