Quentin F. Stout
EECS Department, 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. 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 coverings, packings, mispackings, colorings, maximal matching, partitions, independent sets, tilings, codes, colorings, etc. In addition, there are straightforward algorithm extensions to several different types of domination, including perfect domination (which is the same as perfect error-correcting codes) and to other ways of composing graphs.
Here are some open problems and conjectures related to this paper.
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). 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: codes, 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, graph theory, discrete mathematics, computer science, algorithms
Complete paper. This paper appears in Congressus Numerantium 105 (1994), pp. 116-128.
|
Copyright © 2005-2009 Quentin F. Stout |