Premium
Variants of Visibility and their Complexity
Author(s) -
Schuchardt Dietmar,
Hecker HansDietrich
Publication year - 1998
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19980440411
Subject(s) - visibility , cover (algebra) , vertex (graph theory) , vertex cover , mathematics , combinatorics , geography , time complexity , graph , mechanical engineering , meteorology , engineering
Abstract First we give an overview about variants of visibility and related problems. Then we prove that some guarding and covering problems are NP‐hard for ortho‐polygons with holes, using a so‐called vertex cover technique.