The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.1 / (1999))
Finding Separator Cuts in Planar Graphs within Twice the Optimal
Naveen Garg, Huzur Saran, Vijay V. Vazirani,
Pages. 159-179
Abstract
Contents 1. Introduction 2. Preliminaries 3. Overview of the algorithm 4. Analysis of the dot-box algorithm 5. Structural properties of our solution, and a computationally easier definition of net-cost 6. Onto planar graphs 6.1. Associating cycles with sets 6.2. Transfer function 7. Finding 7.1. Obtaining net-weight and net-cost from transfer functions 7.2. The approach to finding 7.3. Overcoming nonsimple cycles 7.4. A key theorem 8. Finding $\square$ sets 9. Running time 10. Dealing with binary weights 10.1. $b$-balanced cut 10.2. Sparsest cut 11. Open problems
Key words separators, planar graphs, approximation algorithms
Mathmatical Subject Classification 68Q25, 68Q35, 90C27, 05C85