The \textsc{Red-Blue Separation} problem on graphs

DOI10.1016/j.tcs.2023.114061arXiv2211.08283OpenAlexW4383197825MaRDI QIDQ6168089

Ralf Klasing, Tuomo Lehtilä, Subhadeep Ranjan Dev, Florent Foucaud, Sanjana Dey

Publication date: 8 August 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2211.08283

zbMATH Keywords

identifying codesdominating setsseparating sets

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterizations of test cover with bounded test sizes
• Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs
• A simplified NP-complete satisfiability problem
• Parameterized graph separation problems
• On separating systems
• Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
• Approximation algorithms for the test cover problem
• Identification of points using disks
• On separating points by lines
• The \textsc{red-blue separation} problem on graphs
• Extremal graphs for the identifying code problem
• Locating and total dominating sets in trees
• Induced subsets
• SEPARATING POINTS BY AXIS-PARALLEL LINES
• Identifying Codes in Hereditary Classes of Graphs and VC-Dimension
• The Complexity of Multiterminal Cuts
• On a new class of codes for identifying vertices in graphs
• An induced subgraph characterization of domination perfect graphs
• Revisiting and Improving Upper Bounds for Identifying Codes
• Analytical approach to parallel repetition
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

This page was built for publication: The \textsc{Red-Blue Separation} problem on graphs