The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, $k$-MST, and Related Problems
Joseph S. B. Mitchell,
Pages. 1298-1309
Abstract
Contents 1. Introduction
2. $m$-Guillotine subdivisions
3. The main theorem
4. Some applications
4.1. Steiner tree
4.2. TSP
4.3. $k$-MST
5. Conclusion
Key words pproximation algorithms, polynomial-time approximation scheme, traveling salesperson problem, $k$-MST, Steiner minimal trees, guillotine subdivisions, computational geometry
Mathmatical Subject Classification 68Q25, 68R10, 68U05