Week 2 Topic: Distance and Centrality Concepts in Graphs Massive Graph Algorithmics Joint work with J. Abello and J. Westbrook Communications networks and the traffic they carry can be modeled
as graphs. For example, each customer is a vertex, and a transaction
(e.g., a telephone call) between two customers is an edge. The resulting
graphs are quite large: the AT&T voice network carries two to three
hundred million calls on a typical business day; over time, the number of
customers seen is also two to three hundred million. The induced graphs
contain a wealth of information, but standard graph algorithms assume
that graphs fit in main memory and do not scale to process such massive
graphs efficiently.
I will review one standard model of algorithmic complexity and show how
it breaks down for out-of-core data. I will then introduce a newer
model that stresses data transfer over computation and demonstrate how
it leads to some effective graph algorithms. Finally, I will show some
of the data we have been able to analyze as a result.
Mutually eccentric vertices in graphs The distance between a pair of vertices u and v is the length of a shortest
path joining u and v. The eccentricity e(v) of vertex v is the distance to
a vertex farthest from v. The center of graph G is the set of vertices
with minimum eccentricity, and the periphery is the set of vertices with
maximum eccentricity. In a graph G, an eccentric vertex of v is a vertex
farthest from v in G, that is, a vertex u for which d(u,v) = e(v). Given a
set X of vertices in G, the vertices of X are mutually eccentric provided
that for any pair of vertices u and v in X, u is an eccentric vertex of v
and v is an eccentric vertex of u. We discuss problems concerning sets of
mutually eccentric vertices in graphs with particular attention paid to
mutually eccentric central vertices and mutually eccentric peripheral
vertices. Average Distance in Graphs The average distance of a connected graph G is the average of
the distances between all pairs of vertices of G. The average
distance has been investigated by several authors and under
different names, such as mean distance, total distance,
transmission, routing cost, and Wiener index.
In this talk we present a survey of results on the average
distance of graphs. We give several bounds relating it to
other graph invariants, in particular to order, size, minimum
degree, independence number, domination number, and matching
number. We also discuss algorithmic aspects of the average distance. We
present results on the computation of the average distance and
on the problem of finding a minimum average distance spanning
tree of a given graph. We conclude the talk with a brief investigation of generalisations
of the average distance. The Path Partition Conjecture and its Cousins Joint work with M. Frick The detour order T(G) of a graph G = (V,E) is the order of a
longest path of G. A partition {A,B} of V is called an (a,b)-partition if
T(G[A]) <= a and T(G[B]) <= b.
The Path Partition Conjecture is the following: For any graph G, with detour order T(G) = a + b, there
exists an (a,b)-partition of the vertices of G. A subset K of V is called a Pn-kernel of
G if it is Pn-free and every vertex of V - K is adjacent
to an endvertex of a Pn-1. We examine two (possibly stronger) conjectures: Conjecture 2: Every graph has a Pn-kernel for every positive integer n. Conjecture 3: If M is a maximum Pn+1-free subgraph of G, with
n < T(G), then T(G - M) <= T(G) - n. We investigate the relationships among these conjectures and find classes
of graphs for which the conjectures hold. Radio labelings of graphs Joint work with G. Chartrand, F. Harary and P. Zhang Informally, a radio labeling is a simplified, abstract model of
FCC regulations governing the assignment of frequencies to commercial
FM stations. Formally, a radio labeling of a connected graph G is
an assignment of distinct positive integers to the vertices of G, with x
labeled c(x), such that d(u,v) + |c(u)-c(v)| >= 1 + diam G
for every two distinct vertices u,v of G. The
radio number rn(c) of a radio labeling c of G is the
maximum label assigned to a vertex of G. The radio number
rn(G) of G is min{rn(c)} over all radio labelings c of
G. We shall discuss the radio numbers of several classes of graphs and
also describe some more general bounds. We shall probably
also mention related work on the antipodal chromatic number
and radio colorings.
University of Colorado at Denver * Mesa State College, Grand Junction, Colorado Knight Covers of Rectangular Boards A set of Knights covers a board if they attack every Knightless square.
What is the minimum size of a Knight cover for a kxn board? By finding
periodicity in an algorithm of Hare and Hedetniemi, we answer this
question and give minimum covers for all n when k<=10. We also count
minimum covers for k<=9 and n<=49.
Optimal location of a mesometric facility Mesometric facilities are a "third generation" class, neither purely
attractive nor purely obnoxious. Motivating scenarios, including some in non-
"physical" spaces, are identified. The corresponding optimization problems are
nasty (non-convex, non-concave): applicability of "dc programming" algorithms is
explored. A complete analytical solution for a natural class of 1-dimensional
models is sketched, including verification of a "migration hypothesis"
conjectured to hold more generally. For 1-center problems on a network with n
vertices and m edges, the domain is shown reducible, with effort low-order
polynomial in (n,m), to a certain "finite dominating set" of low-order
polynomial size, a result in the spirit of that of Church and Garfinkel (1978)
for obnoxious facilities. Finally, various further research issues are
identified, in particular difficulties in the modelling of multi-facility
situations. A central appendage number of a uniform central graph A graph is called a uniform central graph if the eccentric sets of all
central vertices are the same. A central appendage number of a graph G,
denoted by Aucg(G), is the minimal number of vertices to be added to
G such that the resulting graph H is a uniform central graph with
C(H)=G (C(H) is the center of H). In this paper we prove that for any
graph G, 2<= Aucg(G)<= 6. Also we characterize all graphs G for
which Aucg(G) = 2, 4, or 6. Improved Approximation Algorithms for Fault Tolerant Facility Location We consider a generalization of the classical facility location
problem, where we require the solution to be fault-tolerant. Every demand point j is served by rj
facilities instead of just one. The facilities other than the
closest one are ``backup'' facilities for that demand, and will be
used only if the closer facility (or the link to it) fails. Hence,
for any demand, we assign non-increasing weights to the routing
costs to farther facilities. The cost of assignment for demand j
is the weighted linear combination of the assignment costs to
its rj closest open facilities. We wish to minimize the sum of
the cost of opening the facilities and the assignment cost of each
demand j. We obtain a factor 4 approximation to this problem
through the application of various rounding techniques to the linear
relaxation of an integer program formulation. We further improve
this result to 3.16 using randomization and to 2.47 using greedy
local-search type techniques.
Power domination in graphs applied to electrical power networks The problem of monitoring an electrical power system by placing as few measurement devices in the system as possible is closely related to the well known vertex covering and dominating set problems in graphs. We consider the graph theoretical representation of this problem as a variation of the dominating set problem and define a set S to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S (following a set of rules for power system monitoring). The power domination number of a graph G is the minimum cardinality of a power dominating set of G. We show that the power dominating set problem (PDS) is NP-complete even when restricted to bipartite graphs or chordal graphs. On the other hand, we give an linear algorithm to solve PDS for trees. We also investigate theoretical properties of the power domination number in graphs. Locating Roman Legions Optimally Joint work with E.J. Cockayne, P.A. Dreyer, Jr. and S.M. Hedetniemi A Roman dominating function (RDF) on a network G = (V,E)
is an assignment f: V -> {0,1,2} of Roman Legions
to some of the locations in the network, such
that every location u having no Legion assigned
to it (f(u) = 0) is adjacent to at least one location
v having two Legions assigned to it (f(v) = 2).
If a location u has no Legion assigned to it, then it
must be possible to send a Legion to defend it from
a neighboring location v, subject to Emperor Constantine's
decree that no Legion can leave a location v to defend
another location unless a second Legion is also stationed at v.
The cost of a Roman dominating function is the total
number of Legions assigned to locations in the graph.
We study the graph theoretic and computational aspects
of this historical facility location problem.
Generalized eccentricity, radius and diameter in graphs For a vertex v and a (k-1)-element subset P of vertices of a
graph, one can define the distance from v to P in various
ways, including the minimum, average, and maximum distance from v
to P. Associated with each of these distances, one can define the
k-eccentricity of the vertex v as the maximum distance over all P,
and the k-eccentricity of the set P as the maximum distance over all v.
If k=3D2 one is back with the normal eccentricity. We study here the
properties of these eccentricity measures, especially bounds on the
associated radius (minimum k-eccentricity) and diameter (maximum
k-eccentricity). Domination-good and domination-bad vertices in trees For a graph G = (V,E), a set S of V(G) is a dominating set if every vertex
in V-S is adjacent to some vertex in S. A vertex
v in V(G) is called good if it is an element of a dominating set of minimum
cardinality in G; otherwise, the vertex is
called bad. Let g(G) and b(G) denote the number of good and bad vertices,
respectively, of G. Then a graph G is classified
according to its good and bad vertices as follows: G is
domination-excellent if g(G) = |V(G)|, is domination-commendable if
g(G) > b(G) > 0, is domination-fair if g(G) = b(G), and is domination-poor
if g(G) < b(G). We investigate trees in each of
these categories. Using degrees to characterize distance-related subgraphs In a connected graph G, the distance of a vertex is defined as the sum
of the distances from v to all other vertices of G. When each vertex is
assigned this value, the median of G is defined as the subgraph induced
by those vertices with minimum distance and the margin of G is the
subgraph induced by the vertices of maximum distance. It is known that
every graph can be the median and margin of other graphs. Also, in a
graph of diameter 2, there is a useful relation between the degree of a
vertex and its distance. In this paper, we extend these ideas in three
ways. First, we define three other subgraphs of G by using the vertices
with the intermediate values of distance: the lower middle, the perfect
middle, and the upper middle. Second, we characterize those graphs that
can be one of the various middle subgraphs, and third, we investigate
for a given graph G and a specified subgraph (median, perfect middle,
etc.), the number of vertices that must be added to V(G) to form a graph
H so that G forms that subgraph of H.
Teachers' Understanding of Math in China and the United States
Characterizations of some location functions on graphs Let X be a finite metric space and S a subset of X. For x in X, let D(x,S)
be a measure of remoteness of x to S, and let L be the function where L(S)
is the set of points x in X for which D(x,S) is minimum. L is called the
median function on X when D(x,S) is the sum of distances of x to points in
S, the mean function on X when D(x,S) is the sum of distances squared, and
the center function on X when D(x,S) is the max of the distances of x to
points in S. This talk will review some recent results characterizing the
median, center and mean functions when X is a tree equiped with the usual
graph metric. Location strategies on graphs A profile on a connected graph G is a sequence of vertices of G. A median of
a profile is a vertex x of G minimizing the sum of the distances between x
and the elements of the profile. The median function M on G returns for each
profile the set of the medians of the profile. We discuss simple strategies
to construct the median function on several classes of graphs. We explore
these ideas in various ways to find strategies for other Location Functions,
and present some open problems.
Steiner distances in graphs and centrality measures and structures The Steiner distance of a set S of vertices in a connected graph G is the
smallest number of edges in a connected subgraph of G that contains S.
For an integer n > 2, the n-eccentricity of a vertex v of G, is the maximum
Steiner distance taken over all n-sets of vertices of G that contain v. The
smallest n-eccentricity among all vertices of G is called the n-radius of G
and the largest n-eccentricity among all vertices of G is called the n-
diameter of G. Relationships between the n-diameter and the n-radius of a
graph are presented. The subgraph induced by the vertices of minimum
n-eccentricity is called the n-center of the graph. The n-distance of a
vertex v in a graph is called the sum of the Steiner distances of all n-sets
of vertices that contain v. The subgraph induced by the vertices of
minimum n-distance is called the n-median of the graph. Structural
characterizations of n-centers and n-medians are presented and it is
shown that these subgraphs can be arbitrarily far apart. Centrality
structures that extend those of the n-center and n-median are defined
and it is shown that every vertex on a shortest path from the n-center to
the n-median of a tree belongs to one of these centrality structures. Some
open problems will also be discussed. Colored Distance in Grid Graphs For a graph facility location problem, each vertex is considered to be
the location of a department or facility. One seeks to optimally locate
these facilities in order to minimize some function of the distances
between 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 ans department i requires a 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 to 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 1x1 grid. Thus each department i has a total of n_i
1x1 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. Meiers and Slater
studied the two color grid graph problem and we discuss preliminary
results on an extension of those results to the general case for t-colors
where t>=2, with an emphasis on the equitable case where all colors occupy
an equal number of vertices in the grid.
Ordered median problems on networks In this paper we address a type of facility location problems on
networks which includes as special cases most of the classical
criteria in the literature. Structural results as well as finite
dominating sets for the optimal locations are developed. We
investigate the existence of a finite set of candidates to be
optimal solutions for a wide range of location problems on
networks: the so called p-facility ordered median problem. Finite
dominating sets (FDS) are known for particular instances of this
problem: p-median, p-center, p-centdian. Our aim is to study the
structure of the set of candidate points to be optimal solutions
for all these problems showing the similarities existing between
them. The frontiers for finding easy finite dominating sets are
shown. For a special subclass of ordered median problems
a polynomial algorithm on trees is proposed.
This algorithm is a generalization of existing ones for the
p-median and the p-centdian problems. Distance problems in graphs whose vertices are graphs Joint work with K.T. Balinska, G.R. Brightwell and J. Szymanski. Let G = (V,E) be a graph such that its vertex set V is a set of graphs and
{X,Y} is in its edge set E if and only if the graph Y can be obtained from
the graph X by the insertion or deletion of a single edge of X. Graphs G of this type, with appropriate embellishments, play a role in a
variety of contexts. For example, G can be the transition digraph for a
random process, the vertices of G can be interpreted as molecular graphs,
or G can be studied strictly with respect to its graph theoretical
properties. Define the distance d(X,Y) between two vertices X and Y of G as the least
number of insertions and/or deletions of edges needed to obtain Y from X,
that is, d(X,Y) is just the graph theoretical distance between X and Y. Our
focus will be on the distance properties of G. Namely, for a given vertex
set we are interested in the diameter, radius, center, and periphery of G.
Vertex sets consisting of (i) all graphs having order n, (ii) all graphs
having order n and maximum vertex degree f, and (iii) all forests having
order n and maximum vertex degree f, will be discussed.
Where is the middle of a tree? There are two very standard "central sets" of vertices in a tree, the
center and the median (which is the same as the branch weight centroid).
Many other "central sets" have been proposed as being the middle of a
tree. In this talk we discuss some "central sets" that we have proposed
for a tree T. First we discuss the set of balance vertices in T, vertices
that might be considered as discrete versions of the center of gravity.
There are trees in which the center, the median, and the set of balance
vertices are singletons, each two of which are far apart. Second, we
discuss a one-parameter family of "central sets," the k-ball branch weight
centroid. This family contains both the center (when k is the radius of
T) and the median (when k = 0). And, third, we discuss a two-parameter
family of "central sets," the k-ball p-path branch weight centroid. This
family actually contains the previous family when p = k+1. We will
compare these families to two of P. Slater's families of "central sets,"
the k-centra and the k-nuclei (which is the same family as Z. Winn's
k-branch weight centroids).
The calculation of average distance in mesh structures Mesh structure is a natural choice among several distributed memory architectures, when studying problems in such areas as image processing, computer vision, and computer geometry, with a parallel architecture. In this paper, we analyze a scalable measurement of average distance between two
specific processors in mesh structures. Such a notion is useful in providing a more global network measurement in characterizing its behavior when carrying out multicasting, as well as unicasting, communication. In particular, we provide a closed-form expression for the average distance between two processors in the case of traditional mesh. For a more sophisticated case, where a tradition mesh is augmented with additional diagonal links, we provide a pretty elegant and telling expression for the same quantity. However, we will show that this quantity, i.e., the average distance between two processors, for this augmented structure cannot be expressed in a closed-form expression, with respect to a fairly general class of "standard operations", namely, hypergeometric terms. Besides suggesting another global measurement of the communication behavior for general computer networks, and deriving concrete results for "popular" mesh structures, this paper provides both positive and negative results regarding the derivation of closed-form expressions for combinatorial quantities, thus is also theoretically interesting. We believe that some of the general techniques used in this paper should be applicable else where when closed-form expression needs to be derived, or its existence is in question. Distance, Centrality and Facility Location Graphs and networks model systems, such as communications and transportation systems, in which costs associated with transmission or carrying times are generally nondecreasing functions of the distance between the points involved.In this context, one might be interested in designing an overall "compact" network (subject to certain constraints) or in selecting points in an existing network at which to place "centrally" located facilities. However, different measures of centrality can identify distinct, and, in fact, arbitrarily far apart, locations as optimal. This introductory lecture will contain a general discussion of
distance, centrality and location questions. Included will be a set of
questions, from elementary (?) to the as yet unsolved to get the week
started. On the average Steiner distance of a graph Joint work with P.A. Dankelmann, O.R. Oellermann For n>1, the average Steiner n-distance of a graph G is the average
Steiner distance over all sets of n vertices in G. We establish
properties of and bounds on the parameter for connected graphs,
with particular reference to trees, 2-connected graphs and k-
chromatic graphs.
Facility Location Problems on Tree Graphs with Different Speeds for Customers and Servers: A Study on Covering Problems Defined by Families of Subtrees In the classical p-center problem on a network there are customers located at the
nodes of the network, and the objective is to locate p servers (centers) in order
to minimize the maximum travel distance between the customers and their respective
nearest servers. If customers travel to the servers, possibly at different speeds,
an appropriate objective is to minimize the maximum travel time. Assuming constant
speeds, the latter case reduces to the classical weighted p-center problem,
where distances are weighted by the customer speeds. A symmetric model, where
servers travel to the customers might be appropriate
for other practical situations. We have been motivated by an application which
unifies both models. Suppose that in an emergency situation a customer places a call
for help. The customer has a vehicle that can start traveling immediately, in
any direction at a given speed. There are p servers (emergency crews) on the
network, and they may also have different speeds. The objective is to minimize the
response time, i.e., find a server that will instantenously start moving towards the
customer, minimizing the travel time elapses till the customer meets the server.
The problem is to find the location of p servers, minimizing the maximum
response time to the customers. We are unware of any previous studies of this
problem, where both customers and servers may move simultaneously at different
velocities. We discuss this generalized center location problem,
and study some of its variations, depending on the nature of the set of points,
where customers and servers are allowed to meet. This generalized p-center problem is clearly NP-hard.
Here we focus on tree networks and study the properties of the mathematical model.
In particular, we present polynomial algorithms. Using Graphs for Facility Location Problems Graph theory is an exciting and rapidly growing area of mathematics rich in
theoretical results as well as applications to real-world problems. Many
situations and structures give rise to graphs. For example, a street
system for a city can be modelled by a graph where each intersection
corresponds to a vertex and each street to an edge. Then an emergency
facility should be placed at a location that minimizes the maximum response
time in the city. The best location of a service facility minimizes the
total distance for everyone in the city to travel to this location. But in
reality, it is common to have a road blocked due to road construction or an
accident. This talk will investigate the best location for facilities when
a road is blocked at random. |