Generalized addressing schemes for data graphs

Abstract

Addressable data graphs enjoy structural properties which are at once mathematically attractive and practically useful. This paper is devoted to studying generalizations of addressability, with a twofold goal. The first aim of the paper is to gain understanding of what features of addressing schemes account for the attractive properties of addressable data graphs. The second purpose of the paper is to seek a variant of the property of addressability, which retains the practical concomitants of the original property, but which is enjoyed by a broader class of data graphs. Two such variants are discovered, quasi-addressability and weak-addressability. Although "most" data graphs do not enjoy any form of addressability, every data graph can be slightly modified to render it quasi or weakly addressable-in sharp contrast to the stringent demands of addressability. However, the added breadth of these new addressabilities is obtained at the expense of the invariance and selectivity which accompany the original property. © 1975 Springer-Verlag New York Inc.