A linear algorithm for minimum 1-identifying codes in oriented trees

DOI10.1016/j.dam.2005.11.007zbMath1103.68130OpenAlexW2046202953MaRDI QIDQ2495905

Sylvain Gravier, Irène Charon, Michel Mollard, Olivier Hudry, Julien Moncel, Antoine C. Lobstein

Publication date: 30 June 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.11.007

zbMATH Keywords

treegraphoriented graphidentifying codelinear algorithm

Mathematics Subject Classification ID

Trees (05C05) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items (14)

Identifying codes in the complementary prism of cycles ⋮ Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets ⋮ Identifying codes in line digraphs ⋮ Extremal Digraphs for open neighbourhood location-domination and identifying codes ⋮ On the size of identifying codes in triangle-free graphs ⋮ Discriminating codes in (bipartite) planar graphs ⋮ Operads of finite posets ⋮ On the minimum size of an identifying code over all orientations of a graph ⋮ Improved bounds on identifying codes in binary Hamming spaces ⋮ Minimal identifying codes in trees and planar graphs with large girth ⋮ On two variations of identifying codes ⋮ Sufficient conditions for a digraph to admit a \((1, \leq \ell )\)-identifying code ⋮ Locating-Domination and Identification ⋮ On the size of identifying codes in binary hypercubes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard.
• Identifying and locating-dominating codes on chains and cycles
• Domination and location in acyclic graphs
• On a new class of codes for identifying vertices in graphs
• Identifying and locating-dominating codes: NP-completeness results for directed graphs
• Identifying codes with small radius in some infinite regular graphs

This page was built for publication: A linear algorithm for minimum 1-identifying codes in oriented trees