ABSTRACT
This paper continues the study of the classes of data graphs which are implementable in a random access memory using “relative addressing” and “relocatable realization”, which was initiated in [1]. A new characterization of the class of rooted (=relative addressable) data graphs yields simple and natural proofs of the preservation of rootedness under broad families of operations for composing data graphs. These positive results somewhat diminish the impact of the general unsolvability of detecting rootedness and free-rootedness (=relocatability) in data graphs.
- 1.Rosenberg, A. L. Data graphs and addressing schemes. Journ. Computer and System Sciences, in press. See also a preliminary version in Proc. 2nd Annual ACM Symposium on Theory of Computing, Northampton, Mass. (1970) 48-61. Google ScholarDigital Library
Index Terms
Addressable data graphs (Extended Abstract)
Recommendations
Restrained domination and its variants in extended supergrid graphs
AbstractDomination problem is a well-known NP-complete problem for general graphs. In this paper, we will study its three variants, including restrained, independent restrained, and restrained-step dominations. A restrained dominating set of a ...
Highlights- Extended supergrid graphs can be applied to computerized sewing machine, 3D printers, and so on.
The 2-Rainbow Domination of Sierpiński Graphs and Extended Sierpiński Graphs
Let G(V, E) be a connected and undirected graph with n-vertex-set V and m-edge-set E. For each v ź V, let N(v) = {u|v ź V and(u, v) ź E}. For a positive integer k, a k-rainbow dominating function of a graph G is a function f from V(G) to a k-bit Boolean ...
An extrinsic characterization of addressable data graphs
Previous characterizations of the class of addressable data graphs have been intrinsic in nature. In this note, the auxiliary concept of a monoid system is used to derive an extrinsic characterization of the class. Specifically, a partial transformation ...
Comments