Variants of Visibility and their Complexity

&
Mathematical Logic Quarterly 44 (4):522-528 (1998)
  Copy   BIBTEX

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

Categories

Add categories

Keywords

Reprint years

DOI

10.1002/malq.19980440411

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,031

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons.Dietmar Schuchardt & Hans-Dietrich Hecker - 1995 - Mathematical Logic Quarterly 41 (2):261-267.
Monotonicity and the Expressibility of NP Operators.Iain A. Stewart - 1994 - Mathematical Logic Quarterly 40 (1):132-140.
Minimizing the Size of Vertexlights in Simple Polygons.Andreas Spillner & Hans-Dietrich Hecker - 2002 - Mathematical Logic Quarterly 48 (3):447-458.
The Computational Complexity of Knot Genus and Spanning Area.Agol Ian, Hass Joel & P. Thurston William - unknown
Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory.F. Stephan & B. Borchert - 2000 - Mathematical Logic Quarterly 46 (4):489-504.
A P‐Completeness Result for Visibility Graphs of Simple Polygons.Jana Dietel & Hans-Dietrich Hecker - 2000 - Mathematical Logic Quarterly 46 (3):361-375.
Fast quantum algorithms for handling probabilistic and interval uncertainty.Vladik Kreinovich & Luc Longpré - 2004 - Mathematical Logic Quarterly 50 (4-5):405-416.
Context-sensitive transitive closure operators.Iain A. Stewart - 1994 - Annals of Pure and Applied Logic 66 (3):277-301.
On P Versus NP for Parameter‐Free Programs Over Algebraic Structures.Armin Hemmerling - 2001 - Mathematical Logic Quarterly 47 (1):67-92.
A P-Completeness Result for Visibility Graphs of Simple Polygons.J. Dietel & H.-D. Hecker - 2000 - Mathematical Logic Quarterly 46 (3):361-376.

Analytics

Added to PP
2014-01-16

Downloads
18 (#858,958)

6 months
4 (#863,447)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references