liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Guarding Polyominoes Under k-Hop Visibility
Open Univ Israel, Israel.
Univ Wisconsin Oshkosh, WI 54904 USA.
Malmö Univ, Sweden.
TU Braunschweig, Germany.
Show others and affiliations
2025 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 87, p. 572-593Article in journal (Refereed) Published
Abstract [en]

We study the Art Gallery Problem under k-hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest path between the respective vertices in the dual graph of the polyomino has length at most k. In this paper, we show that the VC dimension of this problem is 3 in simple polyominoes, and 4 in polyominoes with holes. Furthermore, we provide a reduction from Planar Monotone 3Sat, thereby showing that the problem is NP-complete even in thin polyominoes (i.e., polyominoes that do not a contain a 2×2 block of cells). Complementarily, we present a linear-time 4-approximation algorithm for simple 2-thin polyominoes (which do not contain a 3×3 block of cells) for all k∈N.

Place, publisher, year, edition, pages
SPRINGER , 2025. Vol. 87, p. 572-593
Keywords [en]
-hop dominating set
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-212041DOI: 10.1007/s00453-024-01292-7ISI: 001426817000001Scopus ID: 2-s2.0-85217162620OAI: oai:DiVA.org:liu-212041DiVA, id: diva2:1942468
Note

Funding Agencies|Vetenskpsradet

Available from: 2025-03-05 Created: 2025-03-05 Last updated: 2025-06-17

Open Access in DiVA

fulltext(1161 kB)115 downloads
File information
File name FULLTEXT01.pdfFile size 1161 kBChecksum SHA-512
03864f3da5f6f3bff95ec9724cef5d768ecc6be747c6e10fc40d4c19777017a5986d6bdf2e95db7184ee86219b28edeb77283ee5aa189ce9b74f0de3db74e724
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Schmidt, Christiane
By organisation
Communications and Transport SystemsFaculty of Science & Engineering
In the same journal
Algorithmica
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 116 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 132 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf