A GRAPH APPROXIMATION HEURISTIC FOR THE VERTEX COVER PROBLEM ON PLANAR GRAPHS

Authors
MEEK DL PARKER RG
Citation
Dl. Meek et Rg. Parker, A GRAPH APPROXIMATION HEURISTIC FOR THE VERTEX COVER PROBLEM ON PLANAR GRAPHS, European journal of operational research, 72(3), 1994, pp. 588-597
Citations number
27
Categorie Soggetti
Management,"Operatione Research & Management Science
Journal title
European journal of operational research → ACNP
ISSN journal
03772217
Volume
72
Issue
3
Year of publication
1994
Pages
588 - 597
Database
ISI
SICI code
0377-2217(1994)72:3<588:AGAHFT>2.0.ZU;2-A
Abstract
The vertex cover problem is hard in general and remains so on planar g raphs. On the other hand, it is always solvable on bipartite graphs. I n this paper, we introduce a strategy which creates, from an arbitrary planar graph G, a minimum size bipartite homeomorph of G, say G(H). W e solve the vertex cover problem on G(H) and convert the solution to a cover on G. Tests on a set of sample graphs suggest that the resultin g heuristic performs quite well.