Istituto di Scienza e Tecnologie dell'Informazione     
Ciompi P. Note on an extremal problem arising from the diagnosis of regularly interconnected systems diagnosis of regularly interconnected systems. The document will be submitted to Journal: Theoretical Computer Science, Technical report, 2003.
Motivated by the problem of identifying the faulty units in regular interconnected systems this paper studies the combinatorial problem of the following type: for a graph G(V,E) #V=N and any integer a, what is the minimal number f(G,a) such that the removal of f(G, a) nodes results in a graph with a maximal connected component of a nodes or less. The graphs that are studied are regular (all nodes have the same degree ) or quasi-regular graphs; the main attention is paid to planar and toroidal grids. The main result is: f(G, a) * N min(l(G,b)-2)/(2b+l(G,b)-2); l(G,b) is an isoperimetric function: the lower bound on the edges that must be used to connect the nodes that must be removed to isolate a subgraph of b nodes. Using that inequality we find new and better lower bounds.
Subject Isoperimetric inequalities
System-level diagnosis
Toroidal grids
Planar graph
G.2.2 Graph Theory
B.1.3 Control Structure Reliability, Testing, and Fault.Tolerance
C.1.2 Multiple Data Stream Architectures (Multiprocessors)
05C35 Extremal problems

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional