Approximation algorithms to minimum vertex cover problems on polygons and terrains

• Type: Article in International Scientific Journal
• Date: 2003

Authors

Tomas, AP (Author) FCUP; Bajuelos, AL (Author) Other; Marques, F (Author) Other

Journal

The Journal is awaiting validation by the Administrative Services.

Title: COMPUTATIONAL SCIENCE - ICCS 2003, PT I, PROCEEDINGS

Vol. 34

Pages: 869-878

Indexing

ISI Web of Knowledge - 8 Citations

Scopus - 9 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-000-JDT

DOI: 10.1007/3-540-44860-8_90

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 10