Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity

DOI10.3934/amc.2008.2.403zbMath1180.05055OpenAlexW2078516523MaRDI QIDQ1001641

Emmanuel Charbit, Olivier Hudry, Irène Charon, Gérard D. Cohen, Antoine C. Lobstein

Publication date: 19 February 2009

Published in: Advances in Mathematics of Communications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3934/amc.2008.2.403

zbMATH Keywords

complexitybipartite graphsidentifying codesseparating codesdiscriminating codeslocating-dominating codes

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Linear codes (general theory) (94B05) Bounds on codes (94B65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets ⋮ The \textsc{red-blue separation} problem on graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity ⋮ Identifying path covers in graphs ⋮ Bounds and extremal graphs for total dominating identifying codes ⋮ The \textsc{Red-Blue Separation} problem on graphs ⋮ Extremal Digraphs for open neighbourhood location-domination and identifying codes ⋮ Extremal graphs for the identifying code problem ⋮ Separating codes and traffic monitoring ⋮ Fixed-parameter tractable algorithms for tracking shortest paths ⋮ Watching systems in graphs: an extension of identifying codes ⋮ 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 ⋮ On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds. ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ Locating-Domination and Identification ⋮ Separating Codes and Traffic Monitoring ⋮ On the \textsc{Distance Identifying Set} meta-problem and applications to the complexity of identifying problems on graphs ⋮ Locating-dominating sets and identifying codes in graphs of girth at least 5

This page was built for publication: Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity