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

Abstract (English) |
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 |

1) Download Document PDF |

Open access Restricted Private