|
چکیده
|
For a graph facility location problem, each vertex can be considered to be the location of part of a department. One seeks to optimally locate the departments in order to minimize some function of the distances between departments. Consider a factory with a rectangular planar area. The area is divided into a square mesh, a grid with 1-by-l unit pieces, and each piece is assigned to a department. Members of the same department are not required to exchange information, but they must exchange information with every other member of a di erent department. We seek to minimize the total distance between members of di erent departments. 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 di erent colors. The dual concept of color distance named partition distance. Generally this problem is NP-hard but there are some algorithms for special graphs that they are polynomial. In this talk, It is showed the optimal colored distance solution for the n-by-m grid graph when all colors are of equal size. Also it is presented an polynomial time algorithm for trees. Finally, we will present some open problem conjectures for future works.
|