Abstract
In this work we introduce, characterize, and provide algorithmic results for (k, +)-distance-hereditary graphs. These graphs can be used to model interconnection networks with desirable connectivity properties; a network modeled as a (k, +)-distance-hereditary graph can be characterized as follows: if some nodes have failed, as long as two nodes remain connected, the distance between these nodes in the faulty graph is bounded by k plus the distance in the non-faulty graph. The class of all these graphs is denoted by DH(k, +) By varying the parameter k, classes DH(k, +) form a hierarchy that represents a parametric extension of the well-known class of distance-hereditary graphs, and include all graphs.
Work partially supported by the Italian MURST Project “Teoria dei Grafi ed Applicazioni”.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
H. J. Bandelt and M. Mulder. Distance-hereditary graphs. Journal of Combinatorial Theory, Series B, 41(2):182–208, 1986.
A. Brandstädt, V. B. Le and J. P. Spinrad. Graph classes — a survey. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 1999.
J. Bruck, R. Cypher, and C.-T. Ho. Fault-tolerant meshes with small degree. SIAM J. on Computing, 26(6):1764–1784, 1997.
S. Cicerone and G. Di Stefano. Graph classes between parity and distancehereditary graphs. Discrete Applied Mathematics, 95(1-3): 197–216, August 1999.
S. Cicerone, G. Di Stefano, and M. Flammini. Compact-Port routing models and applications to distance-hereditary graphs. In 6th Int. Colloquium on Structural Information and Communication Complexity (SIROCCO’99), pages 62–77, Carleton Scientific, 1999.
S. Cicerone and G. Di Stefano. Graphs with bounded induced distance. Discrete Applied Mathematics, 108(1-2): 3–21, January 2001.
S. Cicerone and G. Di Stefano. Networks with small stretch number. In Proc. 26th International Workshop on Graph-Theoretic Concepts in Computer Science, WG2000, pages 95–106. Lecture Notes in Computer Science, vol. 1928, Springer-Verlag, 2000.
S. Cicerone, G. Di Stefano, and D. Handke. Survivable networks with bounded delay: The edge failure case (Extended Abstract). In Proc. 10th Annual International Symp. Algorithms and Computation, ISAAC’99, pages 205–214. Lecture Notes in Computer Science, vol. 1741, Springer-Verlag, 1999.
G. D’Ermiliis. Topologie di reti con particolari caratteristiche metriche. Master thesis, Faculty of Engineering, University of L’Aquila, 2000.
G. Di Stefano. A routing algorithm for networks based on distance-hereditary topologies. In 3rd Int. Colloquium on Structural Information and Communication Complexity (SIROCCO’96), 1996.
A. H. Esfahanian and O. R. Oellermann. Distance-hereditary graphs and multidestination message-routing in multicomputers. Journal of Comb. Math. and Comb. Computing, 13:213–222, 1993.
A. M. Farley and A. Proskurowski. Self-repairing networks. Parallel Processing Letters, 3(4):381–391, 1993.
M.R. Garey and D.S. Johnson. Computers and Intractability. A Guide to the Theory of NP-completeness. W.H. Freeman, 1979.
J. P. Hayes. A graph model for fault-tolerant computing systems. IEEE Transactions on Computers, C-25(9):875–884, 1976.
E. Howorka. Distance hereditary graphs. Quart. J. Math. Oxford, 2(28):417–420, 1977.
F. T. Leighton, B. M. Maggs, and R. K. Sitaraman. On the fault tolerance of some popular bounded-degree networks. SIAM J. on Computing, 27(6):1303–1333, 1998.
D. Peleg and A. Schaffer. Graph spanners. Journal of Graph Theory, 13:99–116, 1989.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cicerone, S., D’Ermiliis, G., Di Stefano, G. (2001). (k+) -Disatance- Herediatry Graphs. In: Brandstädt, A., Le, V.B. (eds) Graph-Theoretic Concepts in Computer Science. WG 2001. Lecture Notes in Computer Science, vol 2204. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45477-2_8
Download citation
DOI: https://doi.org/10.1007/3-540-45477-2_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42707-0
Online ISBN: 978-3-540-45477-9
eBook Packages: Springer Book Archive