eCIT - Browse eCIT journal

eCIT

Journal of Computing and Information Technology

Authors

Instructions to authors
Book review submission
Login

Journal staff & reviewers

Volume 10, Number 3 (September, 2002), Pages 189-194

doi:10.2498/cit.2002.03.06

A New Approach for Vertex Guarding of Planar Graphs

Branko Kaučič
Faculty of Education, University of Maribor, Maribor, Slovenia
Borut Žalik
Faculty of Electrical Engineering and Computer Science, University of Maribor, Maribor, Slovenia

Abstract
Vertex guarding is one of many optimisation problems in graph theory with wide area of applications. It is proven to be NP-hard, therefore fast approximative solutions are significant. In the paper, at first, known algorithms are considered, and then a new algorithm working on planar graphs is introduced. The new algorithm is based on the dynamic approach and produces better and faster solutions. Its efficiency among other algorithms is demonstrated experimentally. In addition, ideas to additionally improve the algorithm are presented at the end.

Keywords
vertex guarding, graph, optimisation, approximative optimal algorithm, dynamic programming

Full text (PDF)