Group:Algorithms, Complexity and Cryptography
Title: Minimum Manhattan Networks
Speaker: He Sun Max-Planck Institut for Informatics, Germany
Time: 2011-09-30 13:30-2011-09-30 14:30
Venue: FIT 1-222

Abstract:

Given a set T of n points in the plane, a Manhattan network on T is a graph G with the property that for each pair of points in T, G contains a rectilinear path between them of length equal to their distance in the L_1-metric. The minimum Manhattan network problem is to find a Manhattan network of minimum length, i.e. minimizing the total length of the line segments in the network.

 

In this talk, we will show that the decision version of the MMN problem is strongly NP-complete, using a reduction from the well-known 3-SAT problem, which requires a number of gadgets. The gadgets have similar structures, but play different roles in simulating a 3-CNF formula. Some recent progress on this topic will also be presented in this talk.