A list heuristic for vertex cover |
| |
Authors: | David Avis Tomokazu Imamura |
| |
Affiliation: | a School of Computer Science, McGill University, 3480 University, Montreal, Que., Canada H3A 2A7 b Graduate School of Informatics, Kyoto University, Japan |
| |
Abstract: | We analyze a list heuristic for the vertex cover problem that handles the vertices in a given static order based on the degree sequence. We prove an approximation ratio of at most for a nonincreasing degree sequence, and show that no ordering can achieve an approximation ratio of less than . |
| |
Keywords: | Vertex cover Approximation algorithm List heuristic |
本文献已被 ScienceDirect 等数据库收录! |
|