Buchumschlag

Witness Set: A Visibility Problem in $NP\cap XP$

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Jana, Satyabrata, Pal, Debabrata, Roy, Bodhayan, Roy, Sasanka
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Geometry
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Witness Set in Monotone Polygons: Exact and Approximate
von: Das, Udvas, et al.
Veröffentlicht: (2025)

On Approximating the Dynamic and Discrete Network Flow Problem
von: Manna, Bubai, et al.
Veröffentlicht: (2024)

New Complexity and Algorithmic Bounds for Minimum Consistent Subsets
von: Banik, Aritra, et al.
Veröffentlicht: (2024)

Partial Domination in Some Geometric Intersection Graphs and Some Complexity Results
von: Dutta, Madhura, et al.
Veröffentlicht: (2025)

Maximum Cut on Interval Graphs of Interval Count Two is NP-complete
von: Barsukov, Alexey, et al.
Veröffentlicht: (2022)

Multipacking in Euclidean Metric Space
von: Das, Arun Kumar, et al.
Veröffentlicht: (2024)

The Euclidean $k$-Matching Problem is NP-hard
von: Díaz-Báñez, José-Miguel, et al.
Veröffentlicht: (2025)

Closed cap condition under the cap construction algorithm
von: Sandu, Mercedes, et al.
Veröffentlicht: (2022)

Minsum Problem for Discrete and Weighted Set Flow on Dynamic Path Network
von: Manna, Bubai, et al.
Veröffentlicht: (2024)

The Mutual Visibility Problem for Fat Robots with Lights
von: Alsaedi, Rusul J., et al.
Veröffentlicht: (2022)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
von: Bartlmae, Simon, et al.
Veröffentlicht: (2024)

Small symplectic caps and embeddings of homology balls in the complex projective plane
von: Etnyre, John B., et al.
Veröffentlicht: (2023)

Covering Simple Orthogonal Polygons with Rectangles
von: Roy, Aniket Basu
Veröffentlicht: (2024)

The Zarankiewicz Problem for Polygon Visibility Graphs
von: Ackerman, Eyal, et al.
Veröffentlicht: (2025)

Asymmetric Separation Problem for Bichromatic Point Set
von: Maji, Sukanya, et al.
Veröffentlicht: (2024)

NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
von: Yang, Chao, et al.
Veröffentlicht: (2024)

Multivariate Exploration of Metric Dilation
von: Banik, Aritra, et al.
Veröffentlicht: (2025)

A Framework for the Design of Efficient Diversification Algorithms to NP-Hard Problems
von: Gálvez, Waldo, et al.
Veröffentlicht: (2025)

Geometric Criteria for 6-Functor Formalisms in the Setting of Pullback Formalisms
von: Magen, Roy
Veröffentlicht: (2025)

Subset Selection Problems in Planar Point Sets
von: Balogh, József, et al.
Veröffentlicht: (2024)

Approximating Robot Configuration Spaces with few Convex Sets using Clique Covers of Visibility Graphs
von: Werner, Peter, et al.
Veröffentlicht: (2023)

Dominating Set, Independent Set, Discrete $k$-Center, Dispersion, and Related Problems for Planar Points in Convex Position
von: Tkachenko, Anastasiia, et al.
Veröffentlicht: (2024)

New Lower Bound and Algorithms for Online Geometric Hitting Set Problem
von: De, Minati, et al.
Veröffentlicht: (2024)

Freeze-Tag is NP-hard in 2D with $L_1$ distance
von: Silva, Lucas de Oliveira, et al.
Veröffentlicht: (2025)

Min-1-Planarity is NP-Hard
von: Okada, Yuto
Veröffentlicht: (2026)

Computing the EHZ capacity is NP-hard
von: Leipold, Karla, et al.
Veröffentlicht: (2024)

VF-Plan: Bridging the Art Gallery Problem and Static LiDAR Scanning with Visibility Field Optimization
von: Xiong, Biao, et al.
Veröffentlicht: (2025)

M-Guarding in K-Visibility
von: Bahoo, Yeganeh, et al.
Veröffentlicht: (2025)

Empirical Analysis Of Heuristic and Approximation Algorithms for the The Mutual-Visibility Problem
von: Stojanović, Vanja, et al.
Veröffentlicht: (2025)

Recognizing Visibility Graphs of Polygons with Holes and Internal-External Visibility Graphs of Polygons
von: Boomari, Hossein, et al.
Veröffentlicht: (2018)

Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds
von: Bjerkevik, Håvard Bakke, et al.
Veröffentlicht: (2026)

Optimizing Symbol Visibility through Displacement
von: Gärtner, Bernd, et al.
Veröffentlicht: (2023)

Shortest Paths of Mutually Visible Robots
von: Alsaedi, Rusul J., et al.
Veröffentlicht: (2023)

On $NP \cap coNP$ proof complexity generators
von: Krajicek, Jan
Veröffentlicht: (2025)

Contiguous Allocation of Indivisible Items on a Path
von: Kawase, Yasushi, et al.
Veröffentlicht: (2024)

BlockSets: A Structured Visualization for Sets with Large Elements
von: Novakova, Neda, et al.
Veröffentlicht: (2025)

An Efficient Solution to the 2D Visibility Problem in Cartesian Grid Maps and its Application in Heuristic Path Planning
von: Ibrahim, Ibrahim, et al.
Veröffentlicht: (2024)

Fast Witness Persistence for MRI Volumes via Hybrid Landmarking
von: Williams, Jorge Leonardo Ruiz
Veröffentlicht: (2025)

The Nesting Bird Box Problem is ER-complete: Sharp Hardness Results for the Hidden Set Problem
von: Meijer, Lucas, et al.
Veröffentlicht: (2026)

Generalized k-Cell Decomposition for Visibility Planning in Polygons
von: Bahoo, Yeganeh, et al.
Veröffentlicht: (2025)