×

Colored distance in grid graphs. (English) Zbl 0995.05048

Summary: For a graph facility location problem, each vertex is considered to be the location of a department. One seeks to optimally locate the departments in order to minimize some function of the distances among the departments. For example, consider a plant or factory that has a rectangular planar area where \(L\) is the length and \(W\) is the width. Suppose that there are \(t\) departments, department \(i\) requires to total area of \(n_i\), and the sum of the \(n_i\)’s is equal to \(L* W\), the total area. Members of the same department are not required to talk with each other but must talk with everyone else in each of the other departments. Here, we seek to minimize the total distance between members of different departments. We assume that each member is a \(1\times 1\) grid. Thus each department \(i\) has a total of \(n_i\) \(1\times 1\) grids, but these grids are not required to be adjacent. This problem is a particular instance of the colored distance problem, in which a general graph is colored with \(t\) colors, and the colored distance is the sum of the distances between vertices of different colors. D. L. Meiers and P. J. Slater [J. Comb. Math. Comb. Comput. 31, 65-83 (1999; Zbl 0938.90050)] studied the two color grid graph problem, and we discuss an extension of their results to the general case for \(t\) colors where \(t\geq 2\), with an emphasis on the equitable case where all colors occupy an equal number of vertices in the grid.

MSC:

05C12 Distance in graphs
90B80 Discrete location and assignment

Citations:

Zbl 0938.90050
PDFBibTeX XMLCite