Complexity and approximation for discriminating and identifying code problems in geometric setups
From MaRDI portal
Publication:6107885
DOI10.1007/s00453-022-01073-0arXiv2009.10353MaRDI QIDQ6107885
Sanjana Dey, Florent Foucaud, Arunabha Sen, Subhas C. Nandy
Publication date: 28 June 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2009.10353
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved results on geometric hitting set problems
- Separating collections of points in Euclidean spaces
- Orthogonal segment stabbing
- A simplified NP-complete satisfiability problem
- Discriminating codes in (bipartite) planar graphs
- Hitting sets when the VC-dimension is small
- Label placement by maximum independent set in rectangles
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- Approximation algorithms for the test cover problem
- Shattering a set of objects in 2D
- Identification of points using disks
- Parameterized and approximation complexity of \textsc{Partial VC Dimension}
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On separating points by lines
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
- Demand Hitting and Covering of Intervals
- Undirected single-source shortest paths with positive integer weights in linear time
- SEPARATING POINTS BY AXIS-PARALLEL LINES
- Discriminating codes in bipartite graphs
- Identifying Codes in Hereditary Classes of Graphs and VC-Dimension
- Identifying and Locating–Dominating Codes in (Random) Geometric Networks
- Identifying Codes and Covering Problems
- Priority Search Trees
- On a new class of codes for identifying vertices in graphs
- Star Partitions of Perfect Graphs
- Identifying Codes in Line Graphs
- Covering segments with unit squares
- Discriminating Codes in Geometric Setups
This page was built for publication: Complexity and approximation for discriminating and identifying code problems in geometric setups
