Minimum vertex cover in ball graphs through local search |
| |
| Authors: | Zhao Zhang Weili Wu Lidan Fan Ding-Zhu Du |
| |
| Affiliation: | 1. College of Mathematics and System Sciences, Xinjiang University Urumqi, Xinjiang, 830046, People’s Republic of China
2. Department of Computer Science, University of Texas at Dallas, Richardson, TX, 75080, USA
|
| |
| Abstract: | Using local search method, this paper provides a polynomial time approximation scheme for the minimum vertex cover problem on (d) -dimensional ball graphs where (d ge 3) . The key to the proof is a new separator theorem for ball graphs in higher dimensional space. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
