Explicit construction of linear sized tolerant networks (Q1110541): Difference between revisions

A problem occurring in the study of fault tolerant linear arrays is the construction of a graph with the minimum number of vertices and edges such that after removing all but \(\epsilon\) portion of its vertices or edges, the remaining graph contains a path of some specified length. Suppose \(\epsilon >0\) and m is any integer, \(m\geq 1\). The authors present an explicit construction of graphs G with O(m/\(\epsilon)\) vertices and maximum degree \(O(1/\epsilon^ 2)\) such that after deleting all but \(\epsilon\)-portion of its vertices or edges, the remaining graph contains a path of length m.