Approximation algorithms to minimum vertex cover problems on polygons and terrains Article

Tomás, AP, Bajuelos, AL, Marques, F. (2003). Approximation algorithms to minimum vertex cover problems on polygons and terrains . EURO-PAR 2011 PARALLEL PROCESSING, PT 1, 2657 869-878. 10.1007/3-540-44860-8_90

cited authors

  • Tomás, AP; Bajuelos, AL; Marques, F

authors

abstract

  • We propose an anytime algorithm to compute successively better approximations of the optimum of MINIMUM VERTEX GUARD. Though the presentation is focused on polygons, the work may be directly extended to terrains along the lines of [4]. A major idea in our approach is to explore dominance of visibility regions to first detect pieces that are more difficult to guard. © Springer-Verlag Berlin Heidelberg 2003.

publication date

  • January 1, 2003

published in

Digital Object Identifier (DOI)

start page

  • 869

end page

  • 878

volume

  • 2657