Self-spanner graphs |
| |
Authors: | Serafino Cicerone Gabriele Di Stefano Dagmar Handke |
| |
Affiliation: | aDipartmento di Ingegneria Elettrica, Università dell’Aquila, I-67040 L’Aquila, Italy bFakultät für Mathematik und Informatik, University of Konstanz,78457 Konstanz, Germany |
| |
Abstract: | We introduce the (k,ℓ)-self-spanners graphs to model non-reliable interconnection networks. Such networks can be informally characterized as follows: if at most ℓ edges have failed, as long as two vertices remain connected, the distance between these vertices in the faulty graph is at most k times the distance in the non-faulty graph. By fixing the values k and ℓ (called stretch factor and fault-tolerance, respectively), we obtain specific new graph classes. We first provide characterizational, structural, and computational results for these classes. Then, we study relationships between the introduced classes and special graphs classes (distance-hereditary graphs, cographs, and chordal graphs), and common network topologies (grids, tori, hypercubes, butterflies, and cube-connected cycles) as well. |
| |
Keywords: | Special graph classes Spanners Stretch number Interconnection networks Fault tolerance |
本文献已被 ScienceDirect 等数据库收录! |
|