A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Cycles identifying vertices and edges in binary hypercubes and 2-dimensional tori
Tekijät: Honkala I, Karpovsky MG, Litsyn S
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2003
Journal: Discrete Applied Mathematics
Tietokannassa oleva lehden nimi: DISCRETE APPLIED MATHEMATICS
Lehden akronyymi: DISCRETE APPL MATH
Vuosikerta: 129
Numero: 2-3
Aloitussivu: 409
Lopetussivu: 419
Sivujen määrä: 11
ISSN: 0166-218X
DOI: https://doi.org/10.1016/S0166-218X(02)00579-6
Tiivistelmä
A set of subgraphs C(1), C(2),...,C(k) in a graph G is said to identify the vertices (resp. the edges) if the sets {j: v is an element of C(j)} (resp. {j: e is an element of C(j)}) are nonempty for all the vertices v (edges e) and no two are the same set. We consider the problem of minimizing k when the subgraphs C(i) are required to be cycles or closed walks. The motivation comes from maintaining multiprocessor systems, and we study the cases when G is the binary hypercube, or the two-dimensional p-ary space endowed with the Lee metric. (C) 2003 Elsevier B.V. All rights reserved.
A set of subgraphs C(1), C(2),...,C(k) in a graph G is said to identify the vertices (resp. the edges) if the sets {j: v is an element of C(j)} (resp. {j: e is an element of C(j)}) are nonempty for all the vertices v (edges e) and no two are the same set. We consider the problem of minimizing k when the subgraphs C(i) are required to be cycles or closed walks. The motivation comes from maintaining multiprocessor systems, and we study the cases when G is the binary hypercube, or the two-dimensional p-ary space endowed with the Lee metric. (C) 2003 Elsevier B.V. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali