Quentin F. Stout
Computer Science and Engineering, University of Michigan
Abstract: Let G be a finite graph and let P(n) denote an element from a one-parameter family of graphs, such as a path of length n, a cycle of length n, or a complete binary tree of height n. We are concerned with determining minimum dominating sets of graphs of the form G x P(n). Using dynamic programming and periodic properties of weighted paths in finite state spaces, we give a constant time algorithm to produce a minimum dominating set of G x P(n), for fixed G and all n, for the one-parameter families mentioned above. Previous researchers had used dynamic programming but had obtained only linear-time algorithms. We also show how a closed form expression can be obtained for the minimum domination number of G x P(n).
This algorithmic approach applies to the determination of all minimum dominating sets for G x P(n), and to related problems of packings, mispackings, colorings, coverings, maximal matching, partitions, independent sets, tilings, codes, colorings, etc. In addition, there are straightforward algorithmic extensions to many different types of domination, including perfect domination (which is the same as perfect error-correcting codes) and to other ways of composing graphs, such as tori, fasciagraphs and rotagraphs.
Note that an extended version of this paper is in preparation (and may appear in more than one part because it seems to be getting too long, or may never appear, for the same reason). The omitted proofs will be included, other examples will be given, some computational aspects will be touched on, and more extensions will be given.
Keywords: covering, domination, packing, mispacking, matching, perfect domination, perfect error-correcting codes, colorings, grid graph, product graph, mesh, torus, dynamic programming, finite state spaces, weighted paths
Complete paper. This paper appears in Congressus Numerantium 105 (1994), pp. 116-128.
|
Copyright © 2005-2024 Quentin F. Stout |