Information Technology Reference
In-Depth Information
THE PLANAR SEPARATOR THEOREM
12.8 The
pizza pie graph
G
=(
V
,
E
)
has
n
=
1 vertices that are uniformly spaced
points on a circle as well as a vertex at the center of the circle.
E
consists of the arcs
between vertices on the circle and edges between the central vertex and vertices on the
circle.
When
n
=
12, triangulate
G
by adding edges between vertices on its external face.
Illustrate Lemma
12.6.2
by choosing a cost function
c
and constructing two sets whose
cost at most 2
c
(
V
)
/
3 and a separator containing at most three vertices.
12.9 In a spanning tree for a graph
G
=(
V
,
E
)
the level of a vertex is the length of the path
from the root to it. Given a non-negative cost function on the vertices of
G
totaling
c
(
V
)
, show there is some level
m
such that the cost of vertices at levels less than and
more than
m
each is at most
c
(
V
)
/
2.
12.10 (
Two-Cost Planar Separator Theorem
)Let
G
=(
V
,
E
)
be an
N
-vertex planar graph
having non-negative vertex costs summing to
c
(
V
)
. Show that
V
can be partitioned
into three sets,
A
,
B
,and
C
, such that no edge joins vertices in
A
with those in
B
,
neither
A
nor
B
has cost exceeding 7
c
(
V
)
/
9
,
|
V
|−
|
A
|
and
|
B
|
contain at
mos
t 5
N/
6
vertices, and
C
contains no more than
K
1
√
N
vertices, where
K
1
=
4
(
2
/
3
+
1
)
.
Hint:
Apply the planar separator theorem twice. The first time use it to partition
V
into two sets of about the same size and a separator. If each of the two sets has cost
at most 2
c
(
V
)
/
3, the result holds. If not, make a second application of the planar
separator theorem to the set with larger cost. Show that it is possible to combine sets to
simultaneously meet both the size and cost requirements.
12.11 Let
G
=(
V
,
E
)
be an
N
-vertex planar graph and let
c
be a non-negative cost function
on
V
with t
otal
cost
c
(
V
)
.Let
P
≥
2. Show there are constants 2
P/
3
≤
q
≤
3
P
and
K
2
=
4
(
2
/
3
+
1
)
/
(
1
5
/
6
)
such that
V
can be partitioned into
q
sets,
A
1
,
A
2
,
−
...
,
A
q
such that for 1
≤
i
≤
q
c
(
V
)
/
(
3
P
)
≤
c
(
A
i
)
≤
3
c
(
V
)
/
(
2
P
)
K
2
√
N
,and
B
i
=
V
and there are sets
C
i
,
|
C
i
|≤
−
A
i
−
C
i
such that no edges join
vertices in
A
i
with vertices in
B
i
.
Hint:
When
P
=
2, use the result of Problem
12.10
and combine the vertices of the
separator with the other two sets to satisfy the necessary conditions. When
P>
2,
subdivide any set with cost exceeding
c
(
V
)
/P
into two sets and a separator using the
two-cost planar separator theorem. Assign vertices of the separator to these two sets to
keep the cost in balance.
THE PERFORMANCE OF VLSI ALGORITHMS
12.12 Show that the function defined by the product of three square matrices has a semel-
lective planar circuit size that is quadratic in its number of variables and that it can be
realized by a VLSI chip with
AT
2
that meets the semellective planar circuit size lower
bound.
12.13 Show that the wrapped convolution function
f
(
n
)
n
, can be realized
as an embedded CCC network on a V
L
SI circuit with area
A
and time
T
satisfying
AT
2
=Θ(
n
2
)
for
Ω(log
n
)
2
n
wrapped
:
R
→R
≤
√
n
.
≤
T
Search WWH ::
Custom Search