Degree-Based Spanning Tree Optimization
Gábor Salamon
Broschiertes Buch

Degree-Based Spanning Tree Optimization

approximation algorithms and relationship to graph vulnerability

Versandkostenfrei!
Versandfertig in 6-10 Tagen
32,99 €
inkl. MwSt.
PAYBACK Punkte
16 °P sammeln!
We consider several spanning tree optimization problems all having a measure function which depends only on the degrees of the resulting spanning tree. In addition, all investigated problems are generalizations of the Hamiltonian Path problem and so are NP-hard. As we cannot expect exact polynomial-time solutions, we use the approach of approximation algorithms. We look for a suboptimal solution in polynomial time and prove that it is not farther from the optimal one than a given approximation factor. Beside algorithmic aspects, we also consider the number of spanning tree leaves from a bit mo...