Skip to the main content

Original scientific paper

https://doi.org/10.2498/cit.2002.03.06

A New Approach for Vertex Guarding of Planar Graphs

Borut Žalik
Branko Kaučič


Full text: english pdf 200 Kb

page 189-194

downloads: 651

cite


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

Hrčak ID:

44778

URI

https://hrcak.srce.hr/44778

Publication date:

30.9.2002.

Visits: 1.305 *