In this work we introduce, characterize, and provide algorithmic results for (k,+)-distance-hereditary graphs, k>=0. 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 the distance in the non-faulty graph plus an integer constant k. The class of all these graphs is denoted by DH(k,+). By varying the parameter k, classes DH(k,+) include all graphs and form a hierarchy that represents a parametric extension of the well-known class of distance-hereditary graphs.
(k,+)-distance-hereditary graphs
CICERONE, SERAFINO;G. DI STEFANO
2003-01-01
Abstract
In this work we introduce, characterize, and provide algorithmic results for (k,+)-distance-hereditary graphs, k>=0. 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 the distance in the non-faulty graph plus an integer constant k. The class of all these graphs is denoted by DH(k,+). By varying the parameter k, classes DH(k,+) include all graphs and form a hierarchy that represents a parametric extension of the well-known class of distance-hereditary graphs.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
