Repositório Institucional da Universidade de Aveiro > Escola Superior de Tecnologia e Gestão de Águeda > ESTGA - Artigos >
 Approximation algorithms to minimum vertex cover problems on polygons and terrains
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/8933

title: Approximation algorithms to minimum vertex cover problems on polygons and terrains
authors: Ana Paula Tomás
António Leslie Bajuelos
Fábio Marques
keywords: Computational Geometry, Art Gallery Theorem, Orthogonal Polygons, Vertex cover Problem, Approximation Algorithms
issue date: 2003
publisher: Springer-Verlag
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
URI: http://hdl.handle.net/10773/8933
publisher version/DOI: http://www.springer.com/computer/swe/book/978-3-540-40194-0
source: Computational Science - ICCS 2003
appears in collectionsESTGA - Artigos

files in this item

file description sizeformat
2003 ICCS apt-alb-fm.pdf248.03 kBAdobe PDFview/open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2