close

Вход

Забыли?

вход по аккаунту

?

169

код для вставкиСкачать
Minimum-Weight Cycles in 3-Separable Graphs
Collette R. Coullard, 1 L. Leslie Gardner, 2 Donald K. Wagner 3
1
Department of Industrial Engineering and Management Sciences, Northwestern University,
Evanston, Illinois 60208
2
School of Business, University of Indianapolis, 1400 E. Hanna Avenue, Indianapolis,
Indiana 46227
3
Division of Mathematical, Computer, and Information Sciences, Office of Naval Research,
Arlington, Virginia 22217
Accepted 20 December 1996
Abstract: This paper presents a polynomial-time algorithm for the minimum-weight-cycle problem on
graphs that decompose via 3-separations into well-structured graphs. The problem is NP-hard in general.
Graphs that decompose via 3-separations into well-structured graphs include Halin, outer-facial, deltawye, wye-delta, flat, and twirl–wheel graphs. For each of these classes of graphs, given the decomposition, the algorithm runs in linear time. q 1997 John Wiley & Sons, Inc. Networks 29: 151–160, 1997
1. INTRODUCTION
Many graph-optimization problems that are NP-hard in
general can be solved in polynomial time when restricted
to classes of well-structured graphs. For instance, the traveling-salesman problem (TSP) admits a polynomial-time
algorithm on Halin graphs [4] and, more generally, on
outer-facial graphs [12, 13]. These algorithms use in a
critical way the fact that Halin and outer-facial graphs
decompose via 3-separations into wheels. This paper examines this phenomenon more closely.
The problem considered here is the minimum-weightcycle problem, which is a generalization of the TSP. An
instance of the minimum-weight-cycle problem is given
by a graph G Å (V, E) and a vector of real weights
{w(e)É e √ E}; the problem is to find a cycle of minimum
Correspondence to: D. K. Wagner; e-mail: wagnerd@onrhq.onr.
navy.mil
weight. (Here, a cycle has no repeated vertices and its
weight is the sum of the weights of its edges.) The TSP
reduces to the minimum-weight-cycle problem by subtracting a large positive constant from each edge weight.
In solving the minimum-weight-cycle problem, it clearly
suffices to assume that G is 2-connected. It is also not
hard to see that the problem can be reduced in linear time
to the case where G is 3-connected using the decomposition algorithm of Hopcroft and Tarjan [14].
This paper gives a unified approach for solving the
minimum-weight-cycle problem on several classes of 3connected graphs. The essential property that these
classes have in common is that their members can be
decomposed via 3-separations into well-structured
graphs. For example, consider a Halin graph G Å (V, E).
Then, it is well known that if G is not a wheel then G
has a 3-edge cut such that shrinking one shore of the cut
to a vertex yields a wheel W and shrinking the other yields
a smaller Halin graph H. Applying this decomposition
recursively to H yields a decomposition of G into a set
q 1997 John Wiley & Sons, Inc.
CCC 0028-3045/97/030151-10
151
0757
/ 8u0f$$0757
03-17-97 20:44:01
netwa
W: Networks
0757
152
COULLARD, GARDNER, AND WAGNER
of wheels. Roughly, the present algorithm for solving the
minimum-weight-cycle problem on G proceeds by first
solving the minimum-weight-cycle problem on W. Then,
this information is encoded on H in such a way that
solving the problem on H also solves it on G. Thus,
solving the problem on G is reduced to solving a sequence
of problems on the set of wheels that make up its decomposition.
This rest of this paper consists of five major sections:
Section 2 describes the graph-theoretic preliminaries. Section 3 gives a preview of the algorithm. Section 4 contains
the algorithm; Section 5, its complexity analysis; and Section 6, its proof of correctness. Undefined graph-theoretic
terminology and notation is consistent with Bondy and
Murty [2].
2. DECOMPOSITION OF 3-CONNECTED
GRAPHS
Let G Å (V, E) be a connected graph and F ⊆ E. The
set V (G[F]) > V (G[E 0 F]) is the set of vertices of
attachment of G[F] and is denoted A(G, F). (Here, G[F]
denotes the subgraph of G induced by F.) Note that A(G,
F) Å A(G, E 0 F). For a positive integer k, a k-separation of G is defined to be a partition {E1 , E2 } of E such
that É E1É ¢ k ° É E2É and É A(G, E1 )É Å k. A cyclic kseparation is a k-separation such that both E1 and E2 contain a cycle. For a positive integer n, G is (cyclically) nconnected if the graph G has no (cyclic) k-separation for
k õ n. The graph G is minimally n-connected if it is nconnected, and for every e √ E, G "e has an (n 0 1)separation.
Let G Å (V, E) be a 3-connected graph having a cyclic
3-separation {E1 , E2 }. Let A(G, E1 ) Å {x, y, z}, and
let {e, f, g, t} be a set disjoint from V < E. Consider
the following 3-step procedure: First, add e, f, g, and t
to G[E1 ] and G[E2 ] so that t is a vertex and is adjacent
precisely to x, y, and z via edges e, f, and g, respectively.
Second, contract those edges in {e, f, g} that are incident
to a degree-two vertex with the convention that new vertex that results retains the name t. Finally, if any edges
of {e, f, g} were contracted, then a renaming procedure
is carried out. If g (say) was contracted in the graph
obtained from G[E1 ], then the edge g in the graph obtained from G[E2 ] is renamed to q, where q is the unique
edge of E1 that is incident to z in G[E1 ]. The resulting
set of graphs {G1 , G2 } is a simple decomposition of G;
see Figure 1. The vertex t is the marker vertex associated
with the simple decomposition, and the edges of the set
{e, f, g} incident to t in G1 and G2 are marker edges.
Note that both G1 and G2 are 3-connected.
A decomposition D of G is defined inductively as either
{G} or the set obtained from a decomposition D * of G
by replacing exactly one member H of D * by the members
0757
/ 8u0f$$0757
03-17-97 20:44:01
netwa
Fig. 1.
of a simple decomposition of H. In the latter case, D * is
a refinement of D. A decomposition D is minimal with
respect to some property P if D satisfies P but no refinement of D satisfies P. Two decompositions of G are
equivalent if they differ only in the names used for the
marker edges and vertices. A decomposition D of G is
unique with respect to some property P if D satisfies
P and any other decomposition of D that satisfies P is
equivalent to D.
A wheel is a graph on n / 1 vertices of which n induce
a cycle and the remaining vertex is joined to each vertex
of the cycle by a single edge. A twirl is a complete bipartite graph K3,n with n ¢ 3. A twirl–wheel graph is a 3connected graph that has a decomposition every member
of which is a wheel or a twirl. One motivation for the
consideration of twirl–wheel graphs is from the decomposition theory for minimally 3-connected graphs developed in Coullard et al. [6]; it was shown that twirls and
wheels are two of the three building blocks for the class
of minimally 3-connected graphs.
Theorem 2.1 [6]. Every minimally 3-connected graph
has a unique minimal decomposition with respect to the
property that every member is either cyclically 4-conj
nected, a twirl, or a wheel.
Gardner [10] showed that the minimum-weight-cycle
problem is NP-hard for the class of minimally 3-connected, cyclically 4-connected graphs. Thus, in looking
for a class of minimally 3-connected graphs that admits
a polynomial-time algorithm, it is reasonable to consider
twirl–wheel graphs.
Minimally, 3-connected twirl–wheel graphs include
Halin graphs, which were introduced by Halin [11]. A
graph is a Halin graph if it is a 3-connected, planar graph
that has an embedding in the plane in which the outer
face has an edge in common with every other face. Many
optimization problems can be solved efficiently on Halin
graphs; see, e.g., Syslo and Proskurowski [17] and Coullard and Pulleyblank [5]. As noted in the Introduction,
Halin graphs have a decomposition, every member of
which is a wheel. Indeed, the unique decomposition of a
W: Networks
0757
MINIMUM WEIGHT CYCLES IN 3-SEPARABLE GRAPHS
Halin graph given by Theorem 2.1 consists entirely of
wheels.
Outer-facial graphs generalize Halin graphs. A graph
is outer-facial if it is 3-connected and planar and has an
embedding in the plane in which the outer face has a
vertex in common with every other face. Outer-facial
graphs are not necessarily minimally 3-connected, and so
Theorem 2.1 does not apply. But Hartvigsen and Pulleyblank [12] showed that every outer-facial graph can
be obtained from a Halin graph by contracting some of
the edges of the cycle that define the outer face. Consequently, it is easily shown that every outer-facial has a
decomposition, every member of which is a wheel.
Outer-facial graphs are not the only 3-connected
graphs that decompose into wheels. Another such class
consists of the so-called delta-wye graphs. A 2-connected
graph is a delta-wye graph if it is reducible to a single
edge by a sequence of series, parallel, and delta-wye reductions; a series reduction is the contracting of an edge
incident to a degree-two vertex, a parallel reduction is
the deleting of an edge that is in a 2-cycle (i.e., a cycle
with exactly two edges), and a delta-wye reduction is
first the deleting of the edges of a 3-cycle and then adding
one new vertex and three new edges such that the new
edges join the new vertex to each of the vertices of the
3-cycle. del Greco and Gardner [7] showed that a 3connected graph having at least four vertices is a deltawye graph if and only if it has a decomposition, every
member of which is a wheel. Thus, 3-connected deltawye graphs include outer-facial and thus Halin graphs.
Another class of delta-wye graphs was studied by Chopra
and Johnson [3]. They defined flat graphs as those planar
graphs that have no cube or the planar dual of a cube as
a minor. (A cube is the planar graph that consists of two
vertex-disjoint 4-cycles plus four additional edges, no two
of which are adjacent and each joining the two 4-cycles.
The cube is an example of a cyclically 4-connected graph.
A graph H is a minor of a graph G if H can be obtained
from G by a sequence of edge deletions and contractions.)
Using the ‘‘forbidden-minor’’ characterization of deltawye graphs given in El-Mallah and Colbourn [8], it is
easily shown that flat graphs are delta-wye graphs.
A class of graphs related to delta-wye graphs are wyedelta graphs, which are also known as partial 3-trees (see
[1]) and graphs of tree-width 3 (see [15]). A graph is a
wye-delta graph if it can be reduced to a single edge by
series, parallel, and wye-delta reductions, where a wyedelta reduction is just the inverse of a delta-wye reduction, i.e., first delete a degree-three vertex and then add
three new edges that form a 3-cycle on its neighbors. A
3-connected wye-delta graph is not necessarily a twirl–
wheel graph; the cube provides a counterexample. Indeed,
del Greco and Gardner [7] showed that every 3-connected
wye-delta graph has a decomposition, every member of
which is a twirl, a wheel, or a cube. Note this does not
0757
/ 8u0f$$0757
03-17-97 20:44:01
netwa
153
imply that every 3-connected twirl–wheel graph is a wyedelta graph. The graph in Figure 2 is a minimally 3connected twirl–wheel graph that is not a wye-delta
graph.
One might be tempted to consider the common generalization of delta-wye and wye-delta graphs that arises
by allowing series, parallel, delta-wye, and wye-delta reductions. The class of graphs that are reducible in this
sense includes all planar graphs; this is a result of Epifanov [9] (see also Truemper [18]). The minimum-weightcycle problem, however, is NP-hard on planar graphs.
3. A PREVIEW OF THE ALGORITHM
To facilitate the description of the algorithm, it is useful
to consider a simple scenario. Consider an instance of the
minimum-weight-cycle problem on a 3-connected twirl–
wheel graph G Å (V, E). Suppose that G has a simple
decomposition {J, K} such that K is a wheel. Suppose
further that J and K have exactly one marker edge in
common, say e. Let t be the associated marker vertex,
and let {e, f, g} be the set of edges incident to t in J
(and thus in K). Let x, y, and z be the respective other
ends of e, f, and g in J. Thus, e is also incident to x
in K.
Observe that any cycle of G is contained in E(J " t),
is contained in E(K " t), or has a nonempty intersection
with both E(J " t) and E(K " t). (For notational convenience, cycles are equated with their edge sets.) If a cycle
C has a nonempty intersection with both E(J " t) and
E(K " t), then C > E(J " t) [respectively, C > E(K " t)]
together with exactly two of the edges incident to t form
a cycle CJ (respectively, CK ) of J (respectively, K).
Moreover, CJ > {e, f, g} Å CK > {e, f, g}.
Now, assume that C is a minimum-weight cycle of G
which happens to meet both E(J " t) and E(K " t). Assign
a weight of zero to each edge of K that is incident to t,
and allow the remaining edges of K to keep their original
weight. Observe that among all cycles C * of K that satisfy
C * > {e, f, g} Å CJ > {e, f, g}, CK is either a minimumweight cycle of K or a minimum-weight cycle of K that
does not contain x.
Fig. 2.
W: Networks
0757
154
COULLARD, GARDNER, AND WAGNER
Based on the above observations, a procedure for solving the minimum-weight-cycle problem on G might go
as follows: In K, find five cycles: a cycle Cf g that is a
minimum-weight cycle among all cycles that contain f
and g, a cycle C fmg (the ‘‘m’’ stands for miss) that is a
minimum-weight cycle among all cycles that contain f
and g and do not contain (i.e., misses) x, a cycle Cef that
is a minimum-weight cycle among all cycles that contain
e and f, a cycle Ceg that is a minimum-weight cycle among
all cycles that contain e and g, and a cycle CM that is a
minimum-weight cycle among all cycles that have an
empty intersection with {e, f, g}. Finding these five cycles can be done efficiently since K has only O(ÉV ( K)É2 )
cycles. The weights of the first four of these cycles are
now ‘‘loaded’’ onto the vertex t of J. The minimumweight-cycle problem on G is now reduced to the more
general ‘‘minimum-load-cycle’’ problem on J, where the
load of a cycle is the sum of its edge weights plus the
appropriate load from vertex t. To be more specific, now
let CJ be an arbitrary cycle of J. If CJ does not contain
t, then define its load to be equal to its weight [denoted
w(CJ )]; if CJ contains t, then define its load to be w(CJ )
/ l(t, u), where tu is the unique edge of J incident to t
not in CJ , and
computing the loads of the various cycles in the nice
member. This is because, at a general iteration, this member might contain several marker vertices. Given a particular cycle and a marker vertex on the cycle, there are at
most two possible choices for which load to use for the
vertex in computing the load of the cycle [e.g., in the
above example, if CJ contains f and g, then the two
choices are w(Cf g ) and w(C fmg )]. Clearly, if the choice
of load for this marker vertex can be made independently
of the choices for the other marker vertices in the cycle,
then the choice is easy—choose the one that represents
the cheapest feasible extension of the cycle [e.g., w(Cf g )
if CJ does not contain x and w(C fmg ) otherwise]. As it
turns out, the choice of load for a marker vertex is not
necessarily independent of the cycle’s other marker vertices. As will be seen, however, it is sufficient to consider
pairs of marker vertices in the cycle. Specifically, if two
marker vertices of the cycle are joined by a marker edge
or are both joined to a third vertex not on the cycle by
marker edges, then choosing the ‘‘hit’’ load [i.e., w(Cf g )]
for one of the vertices forces the choice of the ‘‘miss’’
load [i.e., w(C fmg )] for the other. This idea is captured
precisely in the next section with the notion of a hit set.
l(t, u)
4. THE MINIMUM-LOAD-CYCLE PROBLEM
Å
w(Cf g )
if u Å x and CJ does not contain u,
w(C fmg )
if u Å x and CJ contains u,
w(Ceg )
if u Å y, and
w(Cef )
if u Å z.
Basically, l(t, u) is acting as a surrogate in CJ ; it
represents the cheapest way of feasibly extending CJ to
a cycle of G. (By ‘‘feasibly,’’ it is meant that the extension of CJ must be a cycle of G. In the above example,
if CJ contains f, g, and x, and Cf g contains x, then extending CJ using Cf g is not a cycle of G. On the other
hand, extending CJ using C fmg does yield a cycle of G.)
Now, the weight of a minimum-weight cycle of G is equal
to either the load of a minimum-load cycle in J or the
previously computed w(CM ), whichever is smaller.
Given this quantity, it is straightforward to backtrack and
actually find a minimum-weight cycle of G.
The algorithm now proceeds recursively on J. At a
general iteration, the algorithm finds a simple decomposition of the current graph such that one member of the
decomposition is ‘‘nice’’ (e.g., a twirl, a wheel, or a
cube). A small number of minimum-load-cycle problems
are solved on this nice member, and the resulting loads
are assigned to the associated marker vertex in the other
member.
One of the main difficulties in the above process is in
0757
/ 8u0f$$0757
03-17-97 20:44:01
netwa
A loaded graph consists of a graph G Å (V, E), a set T
⊆ V of degree-three vertices, a set M ⊆ E such that each
edge of M is incident to a vertex of T, a set L of load
functions, and weight vector w Å {w(e)É e √ E}. By an
abuse of notation, G is used to denote the graph G Å (V,
E) as well as the loaded graph G Å (V, E, T, M, L,
w). A load function is a real-valued function defined on
ordered pairs of adjacent vertices, say (t, u), such that t
√ T. (The vertex u might also be in T.) The load function
is associated with t. The set L consists of two load functions for each pair (t, u), where t √ T; these are denoted
l(t, u) and l m (t, u). Each such pair is assumed to satisfy
l(t, u) ° l m (t, u).
In the context of the previous section, G is a member
of some decomposition; T, the set of its marker vertices;
M, the set of its marker edges; L, the set of its vertex
loads; and w, the vector of its edge weights. [The load
notation here is a refinement of that in the previous section; here l(t, u) represents the ‘‘hit’’ load of t and l m (t,
u ) represents the ‘‘miss’’ load, i.e., in the example of
the previous section, if CJ contains f and g, then l(t, u)
Å w(Cf g ) and l m (t, u) Å w(C fmg ).]
The next definitions are aimed at defining the notion
of a hit set of a cycle discussed previously. Let C be a
cycle of a loaded graph G Å (V, E, T, M, L, w). A vertex
x √ T > V (C) is critical if there exists an edge of M
0 C that joins x to a vertex in V (C) 0 T. A pair of
W: Networks
0757
MINIMUM WEIGHT CYCLES IN 3-SEPARABLE GRAPHS
155
vertices {x, y} ⊆ T > V (C) are incompatible if either
they are joined by an edge in M 0 C or both x and y are
joined to a third vertex z √ T < V (C) by edges in M.
A set H ⊆ T > V (C) is a hit set of C if H does not
contain any critical vertices of C and H contains at most
one vertex from any incompatible pair of C.
Given a cycle C of a loaded graph G Å (V, E, T, M,
L, w) and a hit set H of C, the load of C with respect to
H, denoted l(C, H), is defined to be
LK , wK ): set TK :Å (T > VK ) < {t} and MK :Å (M
> EK ) < M; for each edge e √ EK , set wK (e) :Å 0 if
e is incident to t and wK (e) :Å w(e) otherwise; for
each s£ √ EK with s √ TK , set
l(C, H)
and
:Å ∑ w(e) /
e√C
∑ l(t, u) /
t√H
tu √ E0C
∑
lK (s, £ ) :Å
l(s, J(s))
if £ Å t, and
l(s, £ )
otherwise
l (t, u).
t √ (T>V (C ) )0H
tu √ E0C
l Km (s, £ ) :Å
ALGORITHM MLCP
Input: A loaded 3-connected graph G Å (V, E, T, M, L,
w) that has a decomposition, the members of which belong to a nice class.
if s Å t
l m (s, J(s))
if £ Å t, and
l (s, £ )
STEP 3. Create the loaded graph J Å (VJ , EJ , TJ , MJ , LJ ,
wJ ): set TJ :Å (T > VJ ) < {t} and MJ :Å (M > EJ )
< M; for each edge e √ EJ , set wJ (e) :Å 0 if e √ M
and wJ (e) :Å w(e) otherwise; for each su √ EK with
s √ TK , set
lJ (s, u) :Å
lK (CK (u ) )
if s Å t,
l(s, K(s))
if u Å t, and
l(s, u)
otherwise
and
l Jm (s, u) :Å
lK (C Km (u ) , H Km (u ) )
if s Å t,
l m (s, K(s))
if u Å t, and
l (s, u)
STEP 2. Create the loaded graph K Å (VK , EK , TK , MK ,
netwa
otherwise;
set LK :Å {l(s, £ )És£ √ EK , s √ TK } < {l m (s, £ )És£
√ EK , s √ TK }.
For each neighbor £ of t in K, compute a cycle C£
that is a minimum-load cycle among all cycles of K
that contain t, but do not contain t£ ; compute a cycle
C £m that does not contain t£ , has a hit set H £m that
contains t, and satisfies lK (C £m , H £m ) Å min{lK (C,
H)Ét£ √ C, t √ H}; and compute a cycle CM that is
a minimum-load cycle among all cycles of K that do
not contain t.
m
STEP 1. If G belongs to a nice class, then compute and
output a minimum-load cycle of G and stop. Otherwise, let {J, K} be a simple decomposition of G such
that K belongs to a nice class and J has a decomposition, the members of which belong to a nice class. Let
t be the associated marker vertex, and let M be the
associated set of marker edges.
03-17-97 20:44:01
0
m
Output: A minimum-load cycle of G.
/ 8u0f$$0757
if s Å t
m
The load of C, denoted l(C), is defined to be min{l(C,
H)ÉH is a hit set of C}. The minimum-load-cycle problem
is that of determining a minimum-load cycle of G.
By taking M, T, and L to be empty, the minimumload-cycle problem reduces to the minimum-weight-cycle
problem. Moreover, if the algorithm below for solving
the minimum-load-cycle problem starts with M, T, and
L empty, then throughout the course of the algorithm, M
and T will be the sets of marker edges and marker vertices
of the current graph and L will be the associated load
functions.
The algorithm is now described. Its complexity is given
in Section 5 and its validity is established in Section 6.
A couple of definitions are needed. A class of graphs
will be called nice if the class admits a polynomial-time
algorithm for the minimum-load-cycle problem. Now, let
{J, K} be a simple decomposition of a 3-connected graph
G Å (V, E), and let t be the associated marker vertex.
Then, there exists a natural correspondence between the
neighbors of t in J and those in K. Specifically, for each
neighbor u of t in J, there exists a unique neighbor of t
in K, denoted K(u), such that, in G, either u Å K(u) or
uK(u) √ E; for a neighbor £ of t in K, J( £ ) is defined
analogously.
0757
0
otherwise;
set LJ :Å {lJ (s, u)Ésu √ EJ , s √ TJ } < {l Jm (s, u)Ésu
√ EJ , s √ TJ }.
STEP 4. Apply Algorithm MLCP to the loaded graph J;
let CJ be the output and let HJ be a hit set of CJ such
that lJ (CJ ) Å lJ (CJ , HJ ). If lK (CM ) ° lJ (CJ ), then
output CM and stop. If CJ does not contain t, then
output CJ and stop. If CJ contains t, then let tu √ EJ
W: Networks
0757
156
COULLARD, GARDNER, AND WAGNER
be the edge incident to t not in CJ ; output (CJ < CK (u ) )
0 M if t √ HJ and (CJ < C Km (u ) ) 0 M if t √ HJ ; stop.
j
5. COMPLEXITY OF ALGORITHM MLCP
This section contains the derivation of the complexity of
the algorithm. Specifically, it is first shown that given a
decomposition of a 3-connected graph, the members of
which belong to a nice class, the algorithm runs in polynomial time. Then, it is shown that for all the classes of
graphs introduced in Section 2 the algorithm runs in
O(ÉV É2 ) time. Moreover, if a decomposition is given, the
time is reduced to O(ÉV É). The first result below bounds
the number of members in any decomposition of a 3connected graph G Å (V, E).
Let D be a decomposition of G. It is straightforward
to show, using the fact that a marker vertex has degree
3, that a given marker vertex is in exactly two members
of D. Moreover, the graph having vertex set D with two
vertices being adjacent if and only if the two members
share a marker vertex is a tree, called the decomposition
tree of D. The decomposition tree ‘‘displays’’ several
cyclic 3-separations of G as follows: Let {D1 , D2 } be
the partition of D induced by deleting one particular edge
of the decomposition tree, let E1 be the subset of edges
of G that are contained in some member of D1 , and let
E2 :Å E 0 E1 . Then, {E1 , E2 } is a cyclic 3-separation of
G. (This follows from Lemma 3.3 of Coullard et al. [6].)
Moreover, if {G1 , G2 } is the associated simple decomposition, then Di is a decomposition of Gi for i √ {1, 2}.
(This follows from Theorem 3.8 of Coullard et al. [6].)
A decomposition tree is a star if it has at most one vertex
of degree greater than one.
Lemma 5.1. If G Å (V, E) is a 3-connected graph, then
any decomposition of G has at most max{1,2ÉEÉ 0 12}
members.
Proof. Let D be a decomposition of G. First, consider
the case when the decomposition tree T of D is a star.
Observe that any member of D that has degree one in T
contains at least three edges from G such that each is in
no other member of D. Consequently, the number of
members of D is bounded above by É EÉ/3  / 1. If É EÉ/
3  / 1 ¢ 2É EÉ 0 12, then É EÉ ° 7. The result now
follows since any decomposition of a 3-connected graph
with seven or fewer edges has exactly one member.
Now, consider the case that T is not a star. Then, É EÉ
¢ 8. Choose an edge of T not incident to a degree-one
vertex, and let {D1 , D2 } be the resulting partition of D.
Then, Di is a decomposition of a graph Gi , for i √ {1,
2}, where {G1 , G2 } is a simple decomposition of G
with É E(G1 )É, É E(G2 )É ° É EÉ 0 1. By induction, É Di É
0757
/ 8u0f$$0757
03-17-97 20:44:01
netwa
° max{1, 2É E(Gi )É 0 12} for i √ {1, 2}. Observe that
É E(G1 )É / É E(G2 )É ° É EÉ / 6. Using the fact that
É DÉ Å É D1É / É D2É, the result now follows.
j
In the case that G is a wye-delta or planar (which
includes delta-wye) graph, the above lemma implies an
O(ÉV É) bound on the number of members, since, in these
cases, it is well known that É EÉ Å O(ÉV É). Also, if G
is minimally 3-connected, then it is straightforward to
prove by induction that É EÉ Å O(ÉV É).
Observe that the main work in the algorithm is in
finding the simple decomposition in Step 1 and in computing the minimum-load cycles in Steps 1 and 2. Consider
the latter. Each minimum-load-cycle computation in Step
2 is a variation of the ‘‘pure’’ minimum-load-cycle problem on K. But it is not too hard to see that each of these
variations can be reduced to a pure minimum-load-cycle
problem on K by adjusting the weights on the edges incident to t and the load function lK (t, £ ). For example, to
compute the cycle C £m , make the weight of edge t£ relatively large and the load function lK (t, £ ) relatively small.
Since K is assumed to belong to a nice class, these computations can be done in polynomial time.
Now, consider the problem of finding the simple decomposition in Step 1. By assumption, the input graph G
has a decomposition D, the members of which belong to
a nice class. Given D, the required simple decomposition can be found as follows: Let K be a member of D
that has degree one in the decomposition tree. Then, {D
0 {K}, K} is a partition of D. The corresponding simple
decomposition is {J, K} for an appropriate J. Note, for
the purposes of the algorithm, it is not necessary to actually compute J; it suffices to have a decomposition of J,
the members of which belong to a nice class. Evidently,
such a decomposition is given by D 0 {K}. Consequently, the following has been proved:
Theorem 5.2. Given a decomposition of G, the members
of which belong to a nice class, Algorithm MLCP runs
j
in polynomial time.
The remainder of the section is devoted to determining
a time bound for the algorithm if the G is one of the
graphs discussed in Section 2, namely, delta-wye, wyedelta, and minimally 3-connected twirl–wheel graphs.
In this context, again consider the problem of finding
the simple decomposition of G required in Step 1. The
following lemma solves the problem; for wye-delta
graphs, the lemma is essentially a combination of results
from Matoušek and Thomas [15] and del Greco and Gardner [7].
Lemma 5.3. If is a 3-connected delta-wye graph, a 3-
W: Networks
0757
MINIMUM WEIGHT CYCLES IN 3-SEPARABLE GRAPHS
connected wye-delta graph, or a minimally 3-connected
twirl–wheel graph, and G has more than eight vertices,
then G has a simple decomposition {J, K} such that J is
the same type of graph as G (i.e., delta-wye, wye-delta,
or minimally 3-connected twirl–wheel) with ÉE(J) É õ ÉEÉ
and ÉV ( K) É ° 8. Moreover, this simple decomposition
can be found in O(ÉVÉ) time.
Proof. The first statement of the lemma is proved first;
then the complexity is determined.
Suppose that G is a delta-wye graph. Then, Politof
[16] (also El-Mallah and Colbourn [8]) showed that G
has a cyclic 3-separation {E1 , E2 } such that G[E2 ] is
either the graph in Figures 3(b) or (d) with A(G, E2 )
Å {x, y, z}. Letting {J, K} be the corresponding simple
decomposition, then, evidently, ÉV ( K)É ° 8. Moreover,
J can be seen to be a minor of K with É E(J)É õ É EÉ,
and since delta-wye graphs are known to be closed under
minors (see, e.g., El-Mallah and Colbourn [8]), J is also
a 3-connected delta-wye graph.
The argument in the case that G is a wye-delta graph
is exactly the same with the exception that G[E2 ] is one
of the graphs in Figures 3(a) – (c) with A(G, E2 ) Å {x,
y, z}; in this case, the existence of the appropriate cyclic
3-separation {E1 , E2 } is a result of Arnborg and Proskurowski [1].
Now, suppose that G is a minimally 3-connected twirl–
wheel graph. The first step is to show that G has a cyclic
3-separation {E1 , E2 } such that G[E2 ] is one of the graphs
in Figures 3(a) or (e) with A(G, E2 ) Å {x, y, z}. By
definition, G has a decomposition, every member of
which is a twirl or wheel. Since a twirl has a decomposition, every member of which is a K3,3 , and a wheel has
a decomposition, every member of which is a K4 , G has
a decomposition D, every member of which is either a
K3,3 or a K4 . Let K be a member of D that has degree
one in the decomposition tree, and let {F1 , F2 } be the
cyclic 3-separation of G corresponding to the partition
{D 0 {K}, K} of D. Since K is a K3,3 or a K4 , G has a
cyclic 3-separation {F *1 , F *2 }, where F *2 ⊆ F2 , such that
G[F *2 ] is one of the graphs in Figures 3(a), (b), or (e)
with A(G, F *2 ) Å {x, y, z}. If G[F *2 ] is the graph in
Figure 3(b), then by Theorem 10.54 of Tutte [19], x
(say) has degree three in G. (Theorem 10.54 of Tutte [19]
says, among other things, that a 3-cycle in a minimally 3-
connected graph has at least two vertices of degree three.)
This implies that G has a cyclic 3-separation {E1 , E2 }
such that G[E2 ] is the graph of Figure 3(a) or (e).
The second step is to show that if {J, K} is the simple
decomposition associated with the cyclic 3-separation
{E1 , E2 } of G then J is a minimally 3-connected twirl–
wheel graph with É E(J)É õ É EÉ. The facts that J is
minimally 3-connected and É E(J)É õ É EÉ follow directly from Lemmas 2.5 and 2.6, respectively, of Coullard
et al. [6]. To see that J is a twirl–wheel graph, suppose
otherwise. By Theorem 2.1, J has a decomposition D,
every member of which is either cyclically 4-connected,
a twirl, or a wheel. Since J is not a twirl–wheel graph,
D has a member, say H, that not a twirl or a wheel. From
Lemma 2.6 of Coullard et al. [6], it follows that H is a
minor of G. From the definition of a simple decomposition and the fact that H is cyclically 4-connected, any
decomposition of G must have a member that has a graph
isomorphic to H as a minor. In particular, by considering
the decomposition of G, every member of which is a K3,3
or a K4 , it follows that H is, in fact, a K3,3 or a K4 , a
contradiction.
Now, consider the time complexity of finding the desired simple decomposition. At the heart of finding this
simple decomposition is finding a subgraph of G that is
one of the graphs depicted in Figure 3 with the indicated
vertices of attachment. If G has as a subgraph the graph
of Figure 3(a), then such a subgraph can be found in
O(ÉV É) time using the algorithm for this purpose given
in Matous̆ek and Thomas [15]. If G has as a subgraph
one of the graphs of Figures 3(c) – (e), then such a subgraph can be found in time O(ÉV É) by first finding all of
the degree-three and degree-four vertices of G and then
examining each such vertex to see whether it is in one
of the prescribed subgraphs. Note that examining a given
vertex requires constant time since, in each of the prescribed subgraphs, each edge is incident to either the
given vertex or a neighbor of the given vertex that also
has degree three or four.
Finally, consider the graph of Figure 3(b). To search
for this graph as a subgraph of G, it is assumed that G
does not have any of the graphs of Figures 3(a), (c),
(d), or (e) as subgraphs. Observe, in this case, that G
is a delta-wye or a wye-delta graph. Under the above
Fig. 3.
0757
/ 8u0f$$0757
03-17-97 20:44:01
netwa
157
W: Networks
0757
158
COULLARD, GARDNER, AND WAGNER
assumption, it is claimed that G has as a subgraph the
graph of Figure 3(b) with vertex x (say) having at most
four neighbors other than y. This claim is proved by
induction on the number of edges. Since G does not have
any of the graphs of Figures 3(a), (c), or (d) as subgraphs, by Politof [16] or Arnborg and Proskurowski [1],
it must have the graph of Figure 3(b) as a subgraph with
the indicated vertices of attachment. In G, delete the edge
joining vertices x and y, and call the resulting graph G *.
Note that G * is still a 3-connected delta-wye or a wyedelta graph and, therefore, has one of the graphs of Figures 3(a) – (d) as a subgraph. If G * has any of the graphs
of Figure 3(a), (c), (d), or (e) as a subgraph (call this
subgraph H), then the claim follows since, in this case,
one of the vertices x or y [of the Fig. 3(b) subgraph]
must be a vertex of H that is not a vertex of attachment
of H. On the other hand, if G * does not have any of the
graphs of Figure 3(a), (c), (d), or (e) as a subgraph,
then the claim follows by induction. Given the claim, a
subgraph as in Figure 3(b) can be found, if one exists,
by examining all degree-three vertices of G and for each
one determining if it has two adjacent neighbors. Because
of the claim, this determination can be done in constant
time.
j
O(ÉV É) for some or all of these classes of graphs. (iii)
It is worth a word of explanation as to why Theorem 5.4
is restricted to minimally 3-connected twirl–wheel graphs
as opposed to 3-connected twirl–wheel graphs in general.
The problem is that, unlike minimally 3-connected twirl–
wheel graphs, not every decomposition of a 3-connected
twirl–wheel graph consists of only twirls and wheels. As
an example consider the 3-connected graph in Figure 4.
It is a twirl–wheel graph since it has a decomposition
that consists of four K4’s. But it also has a decomposition
that consists of a K4 and a cube. As observed in (ii), if
one is given a decomposition of 3-connected twirl–wheel
graph that consists of just K4’s and K3,3’s, then the minimum-weight-cycle problem can be solved in linear time.
(v) Wye-delta graphs, delta-wye graphs, and minimally
3-connected twirl–wheel graphs all can be recognized in
polynomial time. Moreover, it is not hard to modify that
algorithm so it accepts any 3-connected graph as input
and as output either produces a minimum-weight cycle
or the conclusion that the input graph is not one of the
prescribed types.
Lemma 5.3 implies that solving the required minimumload-cycle problems on K in Step 2 can be done in constant time. Thus, Theorem 5.1 and Lemma 5.3 imply the
following result:
This section contains the proof of correctness of the algorithm.
Theorem 5.4. If G is a 3-connected delta-wye graph, a 3connected wye-delta graph, or a minimally 3-connected
twirl–wheel graph, then Algorithm MLCP runs in
O( ÉVÉ2 ) time.
j
Proof. The proof is by induction on the number of
recursive calls to Algorithm MLCP; if the number is zero,
which happens only if the original input graph G belongs
to a nice class, then, clearly, the algorithm outputs a correct answer. Thus, assume that the algorithm makes at
least one recursive call. Let J denote the input graph for
the first recursive call to the algorithm. (For convenience,
the notation established in the statement of the algorithm
is used here.) By induction, CJ is a minimum-load cycle
of the loaded graph J. Let C denote the output from Step
4 in the case that lK (CM ) ú lJ (CJ ), i.e., C is equal to CJ ,
(CJ < CK (u ) ) 0 M, or (CJ < C Km (u ) ) 0 M. It is straightforward to verify that C is indeed a cycle of G. The next
step is to show that C has the same load in G as CJ does
in J.
Some remarks are in order: (i) It seems likely that by
doing things a bit more carefully the bound in Theorem
5.4 can be improved to O(ÉV É). Specifically, from the
above analysis, it is the computation of the simple decomposition in Step 1 that requires the most work throughout
the course of the algorithm. The above analysis does not
assume that any information (e.g., the list of degree-three
and degree-four vertices) is passed on from one execution
of Step 1 to the next. Clearly, by doing so, savings can
be achieved. (ii) For the classes of graphs given in
Lemma 5.3, a variation of Algorithm MLCP is to first
compute a decomposition of the input graph into graphs
having a small number of vertices (using the algorithm
given in the lemma, or, perhaps, a different algorithm)
and then generate the simple decompositions required in
Step 1 by ‘‘pulling off ’’ degree-one vertices of the decomposition tree. The complexity of this approach is
O(ÉV É) plus the time required to find the decomposition.
By Lemma 5.3, the time required to find the decomposition is O(ÉV É2 ), but perhaps it can be improved to
0757
/ 8u0f$$0757
03-17-97 20:44:01
netwa
6. CORRECTNESS OF ALGORITHM MLCP
Theorem 6.1. Algorithm MLCP is correct.
Fig. 4.
W: Networks
0757
MINIMUM WEIGHT CYCLES IN 3-SEPARABLE GRAPHS
Claim 1. There exists a hit set H of C in G such that
l(C, H) Å lJ (CJ ).
Proof of Claim 1.
CASE (a). CJ does not contain t. In this case, it is shown
that H :Å HJ satisfies the claim. Since the cycle
C( ÅCJ ) does not contain t, its vertex set is the same
in G as in J. Moreover, any edge joining two vertices
of C in G also does so in J. Similarly, if vertices {x,
y} ⊆ T > V (C) are both joined via edges m and n to
a third vertex z in G, then, since x and y have degree
three in G, x and y are joined via edges m and n to z
in J. Therefore, a critical vertex of C in G is also a
critical vertex of C in J and an incompatible pair of
C in G is an incompatible pair of C in J. It follows
that H is a hit set of C in G. Finally, the definitions
of the load functions for G and J in Step 3 directly
imply that l(C, H) Å lJ (CJ ).
CASE (b). CJ contains t. Let tu be the edge of J incident
to t not in CJ , and let £ :Å K(u). Let H£ be a hit set
of C£ such that lK (C£ , H£ ) Å lK (C£ ). Define CK :Å C£
if t √ HJ and CK :Å C £m if t √
/ HJ . Define HK :Å H£
/ HJ (where H £m is defined
if t √ HJ and HK :Å H £m if t √
in Step 2). Define H :Å (HJ < HK ) 0 {t}. It is now
shown that H satisfies the claim.
Let x be a critical vertex of C in G. Then, x √ T
> V (C) and there exists an edge m √ M 0 C that
joins x to a vertex y √ V (C) 0 T. Since x √ T, it has
/ VJ > VK . Supdegree three in G, and, therefore, x √
pose that x √ VK ; the argument for x √ VJ is similar.
Since x √ VK 0 VJ , it follows that x √ TK > V (CK ).
If y √ V (CK ), then x is a critical vertex of CK in K,
implying that x √
/ HK , and, therefore, x √ H, as required. Thus, assume that y √
/ V (CK ). Then, it must
be that either u Å £ Å y, or u Å y and £ Å x. In either
case, observe that t is critical (with respect to CJ ) in
J since it is joined to y by an edge of MJ and y
√ V (CJ ) 0 TJ [since y √ V (C) 0 T]. This implies
that HK :Å H £m , and it follows from Step 2 that t
√ HK . Now, if u Å £ Å y, then x and t are incompatible
in K (with respect to CK ) since they are both joined
to y by edges of MK . Thus, x √
/ HK , which implies
/ H, as required. On the other hand, if £ Å x,
that x √
then, again, x and t are incompatible in K since they
are joined by the edge m, which is in MK . So, again,
/ H, as required.
x √
Now, consider an incompatible pair of vertices, x
and y, of C in G. First, suppose that x and y are joined
by an edge m √ M 0 C. By definition, both x and y
have degree three in G, and, therefore, neither is in VJ
> VK . First, suppose that x √ VJ and y √ VK . Then, x
Å u and y Å £. It follows that x and t are incompatible
(with respect to CJ ) in J, and y and t are incompatible
0757
/ 8u0f$$0757
03-17-97 20:44:01
netwa
159
(with respect to CK ) in K. Observing that either t
√ HJ or t √ HK , it follows that at most one of x and
y is in H, as required. Now, suppose that {x, y} ⊆ VK ;
the argument for {x, y} ⊆ VJ is similar. Then, m
√ MK , which implies that x and y are incompatible
(with respect to CK ) in K. Thus, at most one of x and
y is in HK and, therefore, H.
Now, suppose that x and y are joined, in G, to a
third vertex z √ T < V (C) via edges m √ M and n
√ M, respectively. By definition, both x and y have
degree three in G, and, therefore, neither is in VJ
> VK . First, suppose that x √ VJ and y √ VK . Then, z
Å u Å £, x Å u, or y Å £. In each case, it is easily
checked that x and t are incompatible (with respect to
CJ ) in J, and y and t are incompatible (with respect
to CK ) in K. Observing that either t √ HJ or t √ HK ,
it follows that at most one of x and y is in H, as
required. Finally, suppose that {x, y} ⊆ VK ; the argument for {x, y} ⊆ VJ is similar. Then, {m, n} ⊆ EK
and z √ VK . It follows that x and y are incompatible
(with respect to CK ) in K. Thus, at most, one of x and
y is in HK and, therefore, H.
Finally, l(C, H) Å lJ (CJ ) / lK (CK , HK ) 0 lJ (t, u)
if t √ HJ and l(C, H) Å lJ (CJ ) / lK (CK , HK )
0 l Jm (t, u) if t √ HJ . From Steps 2 and 3, the last two
terms sum to zero in both equations, and so l(C, H)
Å lJ (CJ ), as required. End of Claim 1.
The next goal is to show that either C or CM is a
minimum-load cycle of G. Let C * be an arbitrary cycle
of G that meets EJ , and let H * be a hit set of C * such
that l(C * ) Å l(C *, H * ). Then, Claims 1 and 2 (below),
together with the induction hypothesis that CJ is a minimum-load cycle of J, imply that l(C) ° l(C * ).
Claim 2. There exists a cycle C 9 of J and a hit set H 9
of C 9 in J such that lJ (C 9, H 9 ) ° l(C * ).
Proof of Claim 2.
CASE (a). C * is a cycle of J. Define C 9 :Å C * and H 9
:Å H *. Note that C 9 does not contain t. Thus, TJ
> V (C 9 ) Å T > V (C 9 ), from which it follows that
H 9 ⊆ TJ > V (C 9 ). Since C 9 does not contain t, any
edge joining two vertices of C 9 in J also does so in
G. Similarly, if vertices {x, y} ⊆ TJ > V (C 9 ) are both
joined via edges m and n to a third vertex z √
/ TJ
< V (C 9 ) in J, then x and y are both joined via edges
m and n to z √
/ T < V (C * ) in G. Therefore, a critical
vertex of C 9 in J is also a critical vertex of C * in G,
and an incompatible pair of C 9 in J is an incompatible
pair of C * in G. It follows that H 9 is a hit set of C 9
in J. Finally, the definitions of the load functions for
G and J in Step 3 directly imply that lJ (C 9, H 9 )
Å l(C * ).
W: Networks
0757
160
COULLARD, GARDNER, AND WAGNER
CASE (b). C * has nonempty intersection with both EJ
and EK . Define C 9 to be the unique cycle of J that
consists of C * > EJ together with two edges of J
incident to t. Consider the set H * > V (C 9 ). Observe
that t √
/ H * > V (C 9 ) and H * > V (C 9 ) ⊆ TJ > V (C 9 ).
Note that any edge joining two vertices of H * > V (C 9 )
in J also does so in G. Similarly, if vertices {x, y}
⊆ H * > V (C 9 ) are both joined via edges m and n to
a third vertex z √
/ TJ < V (C 9 ) in J, then x and y are
joined via edges m and n to z √
/ T < V (C * ) in G.
Therefore, a critical vertex of C 9 in J is also a critical
vertex of C * in G, and an incompatible pair of C 9 in
J is an incompatible pair of C * in G. It follows that
H * > V (C 9 ) is a hit set of C 9 in J. Now, if (H *
> V (C 9 )) < {t} is also a hit set of C 9 in J, then set
H 9 :Å (H * > V (C 9 )) < {t}; otherwise, set H 9
:Å H * > V (C 9 ).
Define C - to be the unique cycle of K that consists
of C * > EK together with two edges of K incident to
t. Then, C * Å (C 9 < C - ) 0 M. Let tu be the unique
edge of J incident to t not in C 9. Now, verifying that
lJ (C 9, H 9 ) ° l(C * ) reduces to showing lJ (t, u)
° lK (C - ) if t √ H 9 and l Jm (t, u) ° lK (C - ) if t
√
/ H 9. By Steps 2 and 3, the first of these inequalities
is true. Similarly, the second is true so long as C - has
a hit set that contains t. So, it suffices to show that if
t √
/ H 9, then H - :Å (H * > V (C - )) < {t} is a hit
set of C -. By an argument analogous to the one above
that showed that H * > V (C 9 ) is a hit set of C 9 in J,
H * > V (C - ) is a hit set of C - in K. Now, using the
facts that H 9 and H * > V (C - ) are hit sets, but that
(H * > V (C 9 )) < {t} is not, it is straightforward to
verify that H - is a hit set of C - in J. End of Claim 2.
Finally, let C * be an arbitrary cycle of G that has empty
intersection with EJ , and let H * be a hit set of C * in G
such that l(C *, H * ) Å l(C * ). Let HM be a hit set of CM
in K such that lK (CM ) Å lK (CM , HM ). Then, C * is also
a cycle of K that does not contain t. Analogous to Claim
2, Case (a), H * is a hit set of C * in K with lK (C *, H * )
Å l(C * ), and so lK (CM ) ° l(C * ). Analogous to Claim
1, Case (a), HM is a hit set of CM in G with l(CM ,
HM ) Å lK (CM ). Therefore, l(CM ) ° l(C * ). The theorem
follows.
j
[ 2]
[ 3]
[ 4]
[ 5]
[ 6]
[ 7]
[ 8]
[ 9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
We thank Dave Hartvigsen for several helpful discussions.
REFERENCES
[1]
0757
[18]
S. Arnborg and A. Proskurowski, Characterization and
recognition of partial 3-trees. SIAM J. Alg. Discr. Methods 7 (1986) 305–314.
/ 8u0f$$0757
03-17-97 20:44:01
netwa
[19]
J. A. Bondy and U. S. R. Murty, Graph Theory with
Applications, North Holland, New York (1976).
S. Chopra and E. L. Johnson, Octahedron and cube free
planar graphs. Unpublished (1989).
G. Cornuéjols, D. Naddef, and W. R. Pulleyblank, Halin
graphs and the travelling salesman problem. Math. Program. 26 (1983) 287–294.
C. R. Coullard and W. R. Pulleyblank, On cycle cones
and polyhedra. Linear Alg. Appl. 114/15 (1989) 613–
640.
C. R. Coullard, L. L. Gardner, and D. K. Wagner, Decomposition of 3-connected graphs. Combinatorica 13
(1993) 7–30.
J. G. del Greco and L. L. Gardner, A note on D 0 Y
and Y 0 D graphs. Submitted.
E. S. El-Mallah and C. J. Colbourn, On two dual classes
of planar graphs. Discr. Math. 80 (1990) 21–40.
G. V. Epifanov, Reduction of a plane graph to an edge
by a star-triangle transformation. Doklady 166 (1966)
13–17.
L. L. Gardner, Studies in 3-connected graphs: a decomposition theory and a decomposition-based optimization
algorithm. PhD. Thesis, Purdue University, West Lafayette, IN (1989).
R. Halin, Studies on minimally n-connected graphs.
Combinatorial Mathematics and Its Applications
(D. J. A. Welsh, Ed.). Academic Press, New York
(1971) 129–136.
D. Hartvigsen and W. R. Pulleyblank, Outer-facial
graphs and the traveling salesman problem. SIAM J. Optim. 4 (1994) 676–689.
D. Hartvigsen and W. R. Pulleyblank, Outer-facial
graphs and the traveling salesman problem: Algorithm
and polyhedron. Research Report, Center for Research
in Business, University of Notre Dame, Notre Dame, IN
(1994).
J. E. Hopcroft and R. E. Tarjan, Dividing a graph into
triconnected components. SIAM J. Comput. 2 (1973)
135–158.
J. Matoušek and R. Thomas, Algorithms finding treedecompositions of graphs. J. Algor. 12 (1991) 1–22.
T. Politof, A characterization and efficient reliability
computation of D –Y reducible networks. PhD. Thesis,
University of California, Berkeley, CA (1983).
M. Syslo and A. Proskurowski, On Halin graphs. Graph
Theory Lagów 1981, Lecture Notes in Mathematics, Vol.
1018, Springer-Verlag, Berlin, Heidelberg (1981) 248–
256.
K. Truemper, On the delta-wye reduction for planar
graphs. J. Graph Theory 13 (1989) 141–148.
W. T. Tutte, Connectivity in Graphs. University of Toronto Press, Toronto, Ontario (1966).
W: Networks
0757
Документ
Категория
Без категории
Просмотров
2
Размер файла
136 Кб
Теги
169
1/--страниц
Пожаловаться на содержимое документа