A new approach for vertex guarding of planar graphs
ITI 2002. Proceedings of the 24th International Conference on Information Technology Interfaces (IEEE Cat. No.02EX534) - Trang 417-422 vol.1
Tóm tắt
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.
Từ khóa
#Graph theory #Dynamic programming #Computer science education #Computer science #Application software #Heuristic algorithms #Radar #TV #Telephony #Radio transmittersTài liệu tham khảo
10.1007/BF02097802
garey, 1979, Computers and Intractability A Guide to the Theory of NP-Completeness
10.1145/800070.802205
zalik, 2001, An incremental construction algorithm for delaunay triangulation based on two-level uniform subdivision, Contributions to Geometric Modelling and Multimedia, 1, 1
lee, 1991, Analyses of visibility sites on topographic surfaces, Int J Geographical Information Systems, 5, 413, 10.1080/02693799108927866
livingston, 1994, Constant time computation of minimum dominating sets, Congressus Numerantium, 105, 116
10.1016/0012-365X(90)90365-O