Identifying Codes in Hereditary Classes of Graphs and VC-Dimension
From MaRDI portal
Publication:3449863
DOI10.1137/14097879XzbMath1323.05098arXiv1407.5833OpenAlexW1745697583MaRDI QIDQ3449863
Aurélie Lagoutte, Zhentao Li, Aline Parreau, Steéphan Thomassé, Nicolas Bousquet
Publication date: 30 October 2015
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1407.5833
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (19)
Identification of points using disks ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Revisiting and Improving Upper Bounds for Identifying Codes ⋮ The \textsc{red-blue separation} problem on graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ Neighbourhood complexity of graphs of bounded twin-width ⋮ A story of diameter, radius, and (almost) Helly property ⋮ Complexity and approximation for discriminating and identifying code problems in geometric setups ⋮ On three domination-based identification problems in block graphs ⋮ The \textsc{Red-Blue Separation} problem on graphs ⋮ The binary locating-dominating number of some convex polytopes ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds. ⋮ Discriminating Codes in Geometric Setups ⋮ On a conjecture regarding identification in Hamming graphs ⋮ Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs ⋮ Bounding the trace function of a hypergraph with applications ⋮ Fast Diameter Computation within Split Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
- Ramsey-type theorems
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Transversals of \(d\)-intervals
- Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- Approximability of identifying codes and locating-dominating codes
- Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
- Dominating sets in \(k\)-majority tournaments.
- On graphs on \(n\) vertices having an identifying code of cardinality \(\lceil \log_{2}(n+1)\rceil\)
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- Scott's Induced Subdivision Conjecture for Maximal Triangle-Free Graphs
- Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension
- Complexity results for identifying codes in planar graphs
- Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
- Discriminating codes in bipartite graphs
- Identifying Codes and Covering Problems
- Structure in Approximation Classes
- On a new class of codes for identifying vertices in graphs
- Identifying Codes in Line Graphs
This page was built for publication: Identifying Codes in Hereditary Classes of Graphs and VC-Dimension
