In [FJ88] the first results dealing with weighted graphs and
dynamic link-cost model are presented. Their nice characterization for
compactness 1 has been extended in [BvLT91] for the linear case,
and finally [BLTT97] proved that a linear time algorithm exists
for the characterization of graphs of compactness k, for every fixed
,
in the setting of dynamic link-cost model.
In this paragraph we consider weighted graphs, that is a pair (G,w)
where G=(V,E) is a graph, and w a non negative function that
assigns a ``weight'' for each edge (the weight is the same for
and
). This weight can take into account the
communication costs along the link between x and its neighbor y.
The cost of a path in a weighted graph is the sum of the
weights of the arcs that compose the path. A minimum path is a
path of minimum cost between its two end-points.
Let us denote by k-
the class of graphs which support a
shortest path k-IRS. Clearly k-
-
because the uniform weight function is a particular case of the model
k-
.
Another model assumes that the addresses of the nodes are fixed once in advance (independently of the link-costs), and then the weights can change. This model takes into account the situation where the link-costs evolve over time, and where the computation of the node-labeling through the network is impossible, whereas the edge-labeling remains locally adjustable in order to achieve a routing path of minimal length.
Similarly, k-
-
because for
-
,
the node-labeling
gives a labeling solution for
every weight function w. Hence k-
-
-
,
and all the lower bounds proved in the uniform
link-cost model hold also for the two other models. We extend the
previous notation to the linear and/to strict IRS in a similar way.
The dynamic link-cost model assumes implicitly that addresses of the nodes cannot be permuted in order to optimize the number of intervals per edge with the routing path lengths. It turns out that Theorem 15 (compactness at most n/4+o(n) for every graph) holds for the fixed link-cost model, but not for the dynamic link-cost model.
For convenience, a statement which holds independently for all the
classes k-
,
k-
,
and k-
is termed with
k-
.
By definition, we set
-
.
Let us start to prove the first point. Let
be an
IRS on G. Consider
.
Let k
be the number of intervals of I. Let
be the
complement of I, and k' its number of intervals. Clearly,
.
Moreover, for the linear cases
,
and k=k' for
cyclic intervals. It implies that
Assume R is non-strict and k is minimum. To show that
-
,
it suffices to show that for n odd the
previous bound decreases by 1. Assume n=2i+1, and that I is
composed of
intervals. Note that I' is
necessarily composed of at least i intervals. Moreover all the
intervals that composed I and I' are single, i.e., of the form
[a]. Indeed if 1 interval (at least) is composed of 2 integers (or
more) then the number of elements in
would be
(i+1)+i+1 =
2i+2=n+1 which is impossible. If
then
appears
as a single interval, so removing it will save one interval. I
contains 1 and n, because I and I' are composed of single
intervals only, and |I| > |I'|. If
then its
insertion will win one interval because
and
are
both single intervals and both belong to I (we can assume
because for
the result is trivial).
To prove
-
it suffices to prove
it for n even. So assume n=2i, and I composed of
intervals. Similarly I and I' are composed of single intervals
only, and thus the insertion or deleting of
in I will
decreases by 1 the number of intervals of I.
Let us show the second point. Consider the nodes labeled 1 and 2.
First consider the case of strict intervals (
or
). Choose w such that w(2,1)=1, w(1,2i+1)=1 for i
integer such that
,
and w(x,y)=3 otherwise. The
shortest paths from 2 to i travels to 1 if i is odd (cost
,
and 3 otherwise). Thus
.
It
is composed of
linear intervals (there are
no consecutive integers in
), and
cyclic
intervals (in the odd case 1 and n can be merged).
For the non-strict intervals (
or
), choose w
such that w(2,1)=1, w(1,2i)=1 for i integer such that
,
and w(x,y)=3 otherwise. The shortest paths from 2 to i
travels to 1 if i is even (
). Hence
.
can belong to
or not,
it does not change the number of intervals of
.
It is
composed of
linear intervals, and
cyclic intervals. This completes the
proof.
The inherent definition of the link-cost model imposes that a graph
can have very different compactness depending on the model (uniform,
fixed or dynamic link-cost). Indeed we have seen in
Theorem 20 that -
.
In the opposite to
the class k-
the fixed and dynamic link-cost models have
known characterizations.
The definition of outerplanar graphs is recalled in Paragraph 3.4.
A G-star is a graph obtained from G by adding zero or more
nodes of degree one to the nodes of G. A centipede is a
P-star, P being a path where some edges of P are replaced by a
K3 (the edge of the path is identified to an edge of K3). A
Y-graph is a tree on 7 nodes with one node of degree 3, and
three nodes of degree 2. Finally, H is a subgraph of minimum
paths of a weighted graph G if H is a subgraph of G, and if
for all ,
all the minimum paths between x and y in
G are wholly contained in H. For unweighted graph G, H is
called subgraph of shortest paths.
According to [vLT94] we have:
The following result proposes a tool to show that a given graph does have not compactness k. It suffices to show that one of its subgraphs of minimum paths is not.
This is also a sufficient condition since G is a subgraph of minimum paths of itself. In the original paper, the result has been mentioned only for the uniform link-cost model. The proof holds for all the models, and can be easily adapted for a version using stretch factor and dilation.
An interesting application of Theorem 52, and the lithium based characterization of 1-linear IRS (cf. Theorem 5) is that every graph that contains a weak-lithium graph, e.g., K1,3, as subgraph of shortest paths does not support any shortest path 1-SLIRS.
Because IRS (with cyclic intervals) are invariant under shifting of the labels modulo n, it is easy to compose graph by union sharing one cut-vertex. The sufficient condition of the next result is an application of Theorem 52.
Here a version for the linear case, and for k=1:
The next result establishes an interesting bridge between minor-taking theory and minimum dynamic cost IRS.
The two last results of Theorem 55 implies that the class
k-
covers a small part of all the graphs since almost all
graphs (even sparse) have a treewidth
,
see [Klo94, Theorem 5.3.2, page 58]. Note that the converse is
false because Theorem 34 shows that there are graphs
of treewidth bounded by k which have unbounded compactness for the
uniform link-cost model, hence for all the models.