Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, May 07, 2009, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Andrea Francke
The Euclidean degree-k minimum spanning tree (E-Dk-MST) problems are defined as follows: Given a set P of n points in the plane and a positive integer w, is there a spanning tree of the points in P with no vertex degree exceeding k that has weight <= w?
The complexity of the E-Dk-MST problems has long been known for all k except k=4. In particular, the E-D2-MST problem corresponds to the path-version of the traveling salesman problem and is NP-complete. The E-D3-MST problem is NP-complete, too, while for k >= 5, the E-Dk-MST problem is solvable in polynomial time. The remaining case, i.e. the E-D4-MST problem, was conjectured to be NP-hard by Papadimitriou and Vazirani in 1984.
In the talk, I will present a proof of the conjecture based on a reduction from vertex cover in cubic planar graphs.
Joint work with Michael Hoffmann.
Automatic MiSe System Software Version 1.4803M | admin login