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
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)
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