Next:
Cuts and Connectivity
Up:
Spanning Trees
Previous:
ND9 MINIMUM GENERALIZED
-
I
NSTANCE
:
Graph
and a weight function
.
-
S
OLUTION
:
A routing tree
T
for
G
, i.e., a tree
T
in which each internal vertex has
degree 3 and the leaves correspond to vertices of
G
.
-
M
EASURE
:
The congestion of the routing tree, i.e., the maximum, for any
edge
e
, of
where
S
is one of the two connected components obtained by deleting
e
from
T
.
-
Good News:
Approximable within
[
223
].
-
Bad News:
Not in A
PX
[
318
].
-
Comment:
The algorithm extends to the case when the routing tree is allowed to have
vertices of higher degree.
If
G
is planar [
318
], or
if
T
is required to be a spanning tree and
G
is
complete [
223
], the problem is solvable in polynomial time.
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997