Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore.

Additionally, libraries can receive an extra 5% discount. Learn More

Additionally, libraries can receive an extra 5% discount. Learn More

Daniel S. F. Alves (Instituto de Matemática, UFRJ, Brazil), E. Elael M. Soares (Escola Politécnica, UFRJ, Brazil), Guilherme C. Strachan (Escola Politécnica, UFRJ, Brazil), Guilherme P. S. Carvalho (Escola Politécnica, UFRJ, Brazil), Marco F. S. Xaud (Escola Politécnica, UFRJ, Brazil), Marcos V. B. Couto (Escola Politécnica, UFRJ, Brazil), Rafael M. Mendonça (UERJ, Brazil), Renan S. Freitas (Escola Politécnica, UFRJ, Brazil), Thiago M. Santos (Escola Politécnica, UFRJ, Brazil), Vanessa C. F. Gonçalves (UFRJ, Brazil), Luiza M. Mourelle (UERJ, Brazil), Nadia Nedjah (UERJ, Brazil), Nelson Maculan (UFRJ, Brazil), Priscila M. V. Lima (Instituto de Ciências Exactas, UFRRJ, Brazil) and Felipe M. G. França (UFRJ, Brazil)

Copyright: © 2014
|Pages: 15

DOI: 10.4018/978-1-4666-4607-0.ch046

Chapter Preview

TopIn order to present the problem and its respective solution in a coherent fashion, some concepts that will be use used in this chapter need to be presented. Given a connected graph *G* and two nodes *v* and *u,* which belong to *G*, if an edge *e* connects *v* and *u*, then *v* and *u* are *neighbors*. This implies that they have a relation of adjacency. If two nodes are *neighbors* in *G* and *D* results from an orientation of *G*, then those two nodes are also *neighbors* in *D*, regardless of the orientation of the edges. The reverse of an orientated edge *e* from *v* to *u* is an orientated edge *f* from *u* to *v*.

For the graph contamination problem, nodes of a graph C are in one of three states: contaminated, clean, and guarded or clean. Contaminated is the initial state of all nodes. A (clean and) guarded node is a node that has received a decontamination agent, which is a tool of the decontamination algorithm and can have different properties regarding creation of new agents and mobility. After leaving a node, the decontamination agent becomes clean. If a clean node has a contaminated neighbor, it becomes contaminated again. This event is called recontamination.

A sink decomposition is a distribution of the nodes of an acyclic connected digraph *D* in numbered layers. The layer of a node is the length of the longest simple path to any sink, or zero if the node is itself a sink. This also results in the property that a node in layer *k*, for 1 ≤ *k* ≤ *l*, where l is the highest layer, has always at least one neighbor in layer *k* – 1.

Search this Book:

Reset

Copyright © 1988-2018, IGI Global - All Rights Reserved