Skoči na glavni sadržaj

Izvorni znanstveni članak

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

A New Approach for Vertex Guarding of Planar Graphs

Borut Žalik
Branko Kaučič


Puni tekst: engleski pdf 200 Kb

str. 189-194

preuzimanja: 447

citiraj


Sažetak

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.

Ključne riječi

Hrčak ID:

44778

URI

https://hrcak.srce.hr/44778

Posjeta: 625 *