Vertex Cover: Further Observations and Further Improvements |
| |
| Authors: | Jianer Chen Iyad A. Kanj Weijia Jia |
| |
| Affiliation: | Department of Computer Science, Texas A&M University, College Station, Texas, 77843-3112, f1;School of CTI, DePaul University, 243 S. Wabash Avenue, Chicago, Illinois, 60604, , f2;Department of Computer Science, City University of Hong Kong, Hong Kong SAR, China, f3 |
| |
| Abstract: | Recently, there has been increasing interest and progress in lowering the worst-case time complexity for well-known NP-hard problems, particularly for the Cover problem. In this paper, new properties for the problem are indicated, and several simple and new techniques are introduced, which lead to an improved algorithm of time O(kn + 1.2852k) for the problem. Our algorithm also induces improvement on previous algorithms for the problem on graphs of small degree. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
