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
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom