DIMACS
The Center for Discrete Mathematics
and Theoretical Computer Science
Reconnect Satellite Conference 2003
Reconnecting Teaching Faculty to the Mathematical Sciences Enterprise
July 16, 2002 - July 23, 2003
(A break day will be provided in between the program schedule)
Centrality in Graphs with Applications to the Theory of Location of Facilities
K. Brooks Reid, California State University San Marcos, breid@csusm.edu
Graphs are used to model many real life situations, and in such
circumstances graph theory serves as a foundational structure to help
explain the world in which we live. One very interesting application
of graph theory is in the theory of the location of facilities in
networks. The theory of location of facilities in networks combines
tools from graph theory, basic analysis, optimization, and complexity
theory. In this series of lectures we use the motivation from the
theory of the location of facilities on networks to concentrate on
some of the underlying graph theory. The goal of this series of talks
is to convey the idea that this subject is a very accessible branch of
applicable combinatorics, rich in problems, and offering an occasional
surprise. Parts of the subject can be incorporated into the
undergraduate classroom, both to illustrate a modern application of
graph theory and to illustrate how applied problems can give rise to
new questions in pure mathematics. The content is very suitable for
stimulating departmental seminars and/or undergraduate lectures.
The major focus of the theory of location of facilities on networks
is to determine where to locate facilities of some sort in a network
of sites that include both potential facility sites and facility user
sites. Facilities might be emergency installations, supply depots,
switching stations, pumping stations, power facilities, transfer
stations, communication devices, obnoxious facilities, or the like.
Location(s) are required that "best" serve the users, where "best" is
measured by criteria given in each particular example, some of which
are required to be optimized over the network. Optimality depends on
criteria usually involving some ideas of distance and costs, and
varies according to the application. Weighted graphs, often referred
to as networks, provide a context for studying these types of
problems. Vertices and edges are assigned weights representing
certain parameters (often some sort of costs) according to the
application. Usually, special sets of points in the network are
sought that are either "central" or "peripheral." Results in the
literature range from the descriptions of optimal locations, to
algorithms for locating optimal locations, to the computational
difficulty in actually determining these optimal locations.
Considerable study has been focused on weighted trees. These issues
have motivated graph theorists to probe many different notions of
central sets of vertices and notions of the "outer fringes" in
ordinary (unweighted) graphs, particularly trees. In such models,
users and facility locations are thought to be restricted to vertices.
However, the graph theoretical origins of centrality precede the
advent of modern location theory as C. Jordan introduced the concepts
of the center of a tree and the branch weight centroid of a tree in
1869.
One major question that we will focus on during these lectures is:
Where is the middle of a tree? We will see that there can be many
different descriptions of the middle of a tree, some of which describe
the same set. However, many descriptions lead to different central
sets. We will also consider multiple centers, central sub-structures,
anti-centrality, axiomatics, and some work on user preferences in
determining locations. In addition, we will consider extensions of
these ideas to graphs in general, and in some cases treat the network
analogs.
Prerequisites: Participants should have good theorem proving skills, curiosity, enthusiasm for a new subject, and an acquaintance with graphs at least at the level of a discrete mathematics course.
References:
[1] N. Graham, R. C. Entringer, and L. A. Szekely, New tricks for old trees: Maps and the pigeonhole principle, Amer. Math. Monthly, 101 (1994), 664-667.
[2] S. L. Hakimi, Optimal locations of switching centers and the absolute centers and medians of a graph, Operations Research, 12 (1964), 450-459.
[3] S. L. Hakimi, Optimal distribution of switching centers in a communication network and some related graph theoretic problems, Operations Research, 12 (1964), 462-475.
[4] J. Halpern, The location of a center-median convex combination on an undirected tree, J. of Regional Science, 16 (1976), 237-245.
[5] G. Y. Handler, Minimax network location: theory and algorithms, Tech. Rept. No. 107. OR Center and FTL-R74-4, Flight Transportation Laboratory, Massachussetts Institute of Technology, Cambridge, 1974.
[6] F. Harary and P. Ostrand, The cutting center theorem for trees, Discrete Math., 1 (1971), 7-18.
[7] C. Jordan, Sur les assemblages des lignes, J. Reine Angew. Math., 70 (1869), 185-190.
[8] E. Minieka, The deliveryman problem on a tree network, Annals of Operations Research, 18 (1989), 261-266.
[9] S. Mitchell, Another characterization of the centroid of a tree, Discrete Math., 24 (1978), 277-280.
[10] O. Ore, Theory of Graphs, American Mathematical Society, Colloquium Publications, XXXVIII, Providence, R.I. (1962).
[11] K. B. Reid, Centroids to centers in trees, Networks, 21 (1991), 11-17.
[12] K. B. Reid, k-ball l-path branch-weight centroids of trees, Applied Discrete Mathematics, 80 (1997), 243-250.
[13] K. B. Reid, Balance vertices in trees, Networks, 34 (1999), 264-271.
[14] K. B. Reid, The latency center of a tree, Preprint (2001).
[15] K. B. Reid and Eli DePalma, Balance in trees, Preprint (2001).
[16] P. J. Slater, Maximin facility location, J. Research of the National Bureau of Standards B, 79B (1975), 107-115.
[17] P. J. Slater, Centers to centroids in graphs, J. Graph Theory, 2 (1978), 209-222.
[18] P. J. Slater, The k-nucleus of a graph, Networks, 11 (1981), 233-242.
[19] P. J. Slater, Accretion centers: a generalization of branch weight centroids, Discrete Appl. Math., 3 (1981), 187-192.
[20] P. J. Slater, On locating a facility to service areas within a network, Oper. Res., 29 (1981), 523-531.
[21] P. J. Slater, A survey of sequences of central subgraphs, Networks, 34 (1999), 244-249.
[22] C. Smart and P. J. Slater, Center, median, and centroid subgraphs, Networks, 34 (1999), 303-311.
[23] B. Zelinka, Medians and peripherians of trees, Arch. Math. (Brno), 4 (1968), 87-95.
The following are some references of books on the theory of locations of facilities. These focus more on the computational aspects of the area.
[1] Mark S. Daskin, Network and Discrete Location: Models, Algorithms, and Applications, John Wiley & Sons (1995).
[2] Z. Drezner (Editor), Facility Location, A Survey of Applications and Methods, Springer, New York (1995).
[3] H. W. Hamacher and Z. Drezner, Location Analysis, Theory and Applications, Springer, New York (2001).
[4] G. Y. Handler and P. B. Mirchandani, Location on Networks, The MIT Press, Cambridge, Massachusetts (1979).
[5] P. B. Mirchandani and R. L. Francis (editors), Discrete Location Theory, John Wiley & Sons, New York (1990).
Journals that publish articles on computational aspects of the area include Networks, Discrete Applied Mathematics, SIAM Journal on Discrete Mathematics, European Journal of Operational Research, Mathematical Programming , among others.
Back to Main Page