CEU Electronic Theses and Dissertations, 2013
| Author | Nadiradze, Giorgi |
|---|---|
| Title | Bounded Diameter Minimum Spanning Tree |
| Summary | In this thesis we showed that the Bounded Diameter Minimum Spanning Tree problem is NP - hard when D > 3 and costs of all edges of the graph are not equal and otherwise it is solvable in polynomial time. We proved that the Bounded Diameter Minimum Spanning Tree problem is solvable in polynomial time when vertices of the graph are points on the real line, points on a circle or vertices in a Caterpillar Tree. The questions left to answer are : how to prove that the Euclidean instance of the Bounded Diameter Minimum Spanning Tree problem is also NP - hard and what happens when the vertices of the graph are the vertices of a general tree not just a Caterpillar Tree, is there polynomial time algorithm to solve this problem or can we prove that it is NP - hard ? |
| Supervisor | Győri Ervin |
| Department | Mathematics MSc |
| Full text | https://www.etd.ceu.edu/2013/nadiradze_giorgi.pdf |
Visit the CEU Library.
© 2007-2021, Central European University