Browse Prior Art Database

On the Construction of General Fault Tolerant Graphs

IP.com Disclosure Number: IPCOM000122300D
Original Publication Date: 1991-Nov-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 1 page(s) / 31K

Publishing Venue

IBM

Related People

Bruck, J: AUTHOR [+3]

Abstract

Disclosed are techniques for adding fault tolerance to arbitrary graphs, h-degenerate graphs, and planar graphs. Specifically, for any general graph G of N nodes, E edges, and maximum degree d, a fault-tolerant graph G' of N+k nodes E' edges and maximum degree d' is constructed such that (1) for any arbitrary k node faults in G', the remaining graph still contains graph G as a subgraph; and (2) d' < 3(k+2)(k+1)d/2.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 100% of the total text.

On the Construction of General Fault Tolerant Graphs

      Disclosed are techniques for adding fault tolerance to
arbitrary graphs, h-degenerate graphs, and planar graphs.
Specifically, for any general graph G of N nodes, E edges, and
maximum degree d, a fault-tolerant graph G' of N+k nodes E' edges and
maximum degree d' is constructed such that (1) for any arbitrary k
node faults in G', the remaining graph still contains graph G as a
subgraph; and (2) d' < 3(k+2)(k+1)d/2.

      If the target graph G to be tolerated is h-degenerate, i.e.,
there exists an ordering of G such that each node has at most h edges
to higher numbered nodes, then E' < (k+2)(k+1)hN/2.  If the target
graph G is planar, then E' < 5(k+2)(k+1)N/2.

      All of the constructions use an ordering of the nodes in the
target graph to define the addition of the edges in the
fault-tolerant graph.  Structural properties of h-degenerate and
planar graphs limit the number of edges which must be added.

      Disclosed anonymously.