✦ LIBER ✦

Fault-tolerant graphs for tori

✍ Scribed by Yamada, Toshinori; Ueno, Shuichi

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 118 KB
Volume: 32
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199810)32:3<181::aid-net2>3.0.co;2-g

No coin nor oath required. For personal study only.

✦ Synopsis

Motivated by the design of fault-tolerant multiprocessor interconnection networks, this paper considers the following problem: Given a positive integer t and a graph H, construct a graph G from H by adding a minimum number D(t, H) of edges such that even after deleting any t edges from G the remaining graph contains H as a subgraph. We estimate D(t, H) for the torus, which is well known as a very important interconnection network for multiprocessor systems.

📜 SIMILAR VOLUMES

Construction schemes for fault-tolerant

Construction schemes for fault-tolerant Hamiltonian graphs

✍ Wang, Jeng-Jung; Hung, Chun-Nan; Tan, Jimmy J. M.; Hsu, Lih-Hsing; Sung, Ting-Yi 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 319 KB 👁 1 views

In this paper, we present three construction schemes for fault-tolerant Hamiltonian graphs. We show that applying these construction schemes on fault-tolerant Hamiltonian graphs generates graphs preserving the original Hamiltonicity property. We apply these construction schemes to generate some know

Node fault tolerance in graphs

✍ Harary, Frank; Hayes, John P. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 405 KB 👁 1 views

A graph G \* is a k-node fault-tolerant supergraph of a graph G , denoted k-NFT( G), if every graph obtained by removing k nodes from G\* contains G. A k-NFT(G) graph G\* is said to be optimal if it contains n + k nodes, where n is the number of nodes of G and G \* has the minimum number of edges am

Cluster fault-tolerant routing in star g

Cluster fault-tolerant routing in star graphs

✍ Gu, Qian-Ping; Peng, Shietung 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 1 views

Fault-tolerant routing is a key issue in computer/ communication networks. We say a network (graph) can tolerate l faulty nodes for a routing problem if after removing at most l arbitrary faulty nodes from the graph the routing paths exist for the routing problem. However, the bound l is usually a w

Sensor network design for fault tolerant

Sensor network design for fault tolerant estimation

✍ M. Staroswiecki; G. Hoblos; A. Aitouche 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 193 KB 👁 2 views

Tolerance graphs, and orders

✍ Felsner, Stefan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 2 views

We show that, if a tolerance graph is the complement of a comparability graph, it is a trapezoid graph, i.e., the complement of an order of interval dimension at most 2. As consequences we are able to give obstructions for the class of bounded tolerance graphs and to give an example of a graph that

Integrated fault-detection and fault-tol

Integrated fault-detection and fault-tolerant control of process systems

✍ Prashant Mhaskar; Adiwinata Gani; Nael H. El-Farra; Charles McFall; Panagiotis D 📂 Article 📅 2006 🏛 American Institute of Chemical Engineers 🌐 English ⚖ 351 KB 👁 2 views