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

Irène Charon; Sylvain Gravier; Olivier Hudry; Antoine Lobstein; Michel Mollard; Julien Moncel

doi:10.1016/j.dam.2005.11.007

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

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

Research output: Contribution to journal › Article › peer-review

Abstract

Consider an oriented graph G = ( V, A ), a subset of vertices C ⊆ V, and an integer r {greater than or slanted equal to} 1; for any vertex v ∈ V, let B_r^- ( v ) denote the set of all vertices x such that there exists a path from x to v with at most r arcs. If for all vertices v ∈ V, the sets B_r^- ( v ) ∩ C are all nonempty and different, then we call C an r-identifying code. We describe a linear algorithm which gives a minimum 1-identifying code in any oriented tree.

Original language	English
Pages (from-to)	1246-1253
Number of pages	8
Journal	Discrete Applied Mathematics
Volume	154
Issue number	8
DOIs	https://doi.org/10.1016/j.dam.2005.11.007
Publication status	Published - 15 May 2006
Externally published	Yes

Keywords

Graph
Identifying code
Linear algorithm
Oriented graph
Tree

Access to Document

10.1016/j.dam.2005.11.007

Cite this

@article{ee5bf20389054ed8b284f2767e162c47,

title = "A linear algorithm for minimum 1-identifying codes in oriented trees",

abstract = "Consider an oriented graph G = ( V, A ), a subset of vertices C ⊆ V, and an integer r \{greater than or slanted equal to\} 1; for any vertex v ∈ V, let Br- ( v ) denote the set of all vertices x such that there exists a path from x to v with at most r arcs. If for all vertices v ∈ V, the sets Br- ( v ) ∩ C are all nonempty and different, then we call C an r-identifying code. We describe a linear algorithm which gives a minimum 1-identifying code in any oriented tree.",

keywords = "Graph, Identifying code, Linear algorithm, Oriented graph, Tree",

author = "Ir{\`e}ne Charon and Sylvain Gravier and Olivier Hudry and Antoine Lobstein and Michel Mollard and Julien Moncel",

year = "2006",

month = may,

day = "15",

doi = "10.1016/j.dam.2005.11.007",

language = "English",

volume = "154",

pages = "1246--1253",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

number = "8",

}

TY - JOUR

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

AU - Charon, Irène

AU - Gravier, Sylvain

AU - Hudry, Olivier

AU - Lobstein, Antoine

AU - Mollard, Michel

AU - Moncel, Julien

PY - 2006/5/15

Y1 - 2006/5/15

N2 - Consider an oriented graph G = ( V, A ), a subset of vertices C ⊆ V, and an integer r {greater than or slanted equal to} 1; for any vertex v ∈ V, let Br- ( v ) denote the set of all vertices x such that there exists a path from x to v with at most r arcs. If for all vertices v ∈ V, the sets Br- ( v ) ∩ C are all nonempty and different, then we call C an r-identifying code. We describe a linear algorithm which gives a minimum 1-identifying code in any oriented tree.

AB - Consider an oriented graph G = ( V, A ), a subset of vertices C ⊆ V, and an integer r {greater than or slanted equal to} 1; for any vertex v ∈ V, let Br- ( v ) denote the set of all vertices x such that there exists a path from x to v with at most r arcs. If for all vertices v ∈ V, the sets Br- ( v ) ∩ C are all nonempty and different, then we call C an r-identifying code. We describe a linear algorithm which gives a minimum 1-identifying code in any oriented tree.

KW - Graph

KW - Identifying code

KW - Linear algorithm

KW - Oriented graph

KW - Tree

U2 - 10.1016/j.dam.2005.11.007

DO - 10.1016/j.dam.2005.11.007

M3 - Article

AN - SCOPUS:33645932613

SN - 0166-218X

VL - 154

SP - 1246

EP - 1253

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 8

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this