Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(1)
Total Length
Subscribe
Academic
Publications
Minimum Manhattan Network is NPComplete
Minimum Manhattan Network is NPComplete,10.1007/s004540119342z,Discrete & Computational Geometry,Francis Y. L. Chin,Zeyu Guo,He Sun
Edit
Minimum Manhattan Network is NPComplete
BibTex

RIS

RefWorks
Download
Francis Y. L. Chin
,
Zeyu Guo
,
He Sun
Given a set T of n points in ℝ2, 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 1metric. 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 paper, we prove that the decision version of the MMN problem is strongly NPcomplete, using a reduction from the wellknown 3SAT problem, which requires a number of gadgets. The gadgets have similar structures, but play different roles in simulating a 3CNF formula.
Journal:
Discrete & Computational Geometry  DCG
, vol. 45, no. 4, pp. 701722, 2011
DOI:
10.1007/s004540119342z
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
More »
References
(14)
The Minimum Manhattan Network Problem: A Fast Factor3 Approximation
(
Citations: 8
)
Marc Benkert
,
Alexander Wolff
,
Florian Widmann
Conference:
Japanese Conference on Discrete and Computational Geometry  JCDCG
, pp. 1628, 2004
The Minimum Manhattan Network Problem  Approximations and Exact Solutions
(
Citations: 7
)
Marc Benkert
,
Takeshi Shirabe
,
Alexander Wolff
Published in 2004.
A Rounding Algorithm for Approximating Minimum Manhattan Networks
(
Citations: 14
)
Victor Chepoi
,
Karim Nouioua
,
Yann Vaxès
Conference:
Approximation Algorithms for Combinatorial Optimization  APPROX
, pp. 4051, 2005
Small Manhattan Networks and Algorithmic Applications for the Earth Mover's Distance
(
Citations: 3
)
Joachim Gudmundsson
Approximating a Minimum Manhattan Network
(
Citations: 23
)
Joachim Gudmundsson
,
Christos Levcopoulos
,
Giri Narasimhan
Journal:
Nordic Journal of Computing  NJC
, vol. 8, no. 2, pp. 219232, 2001