Academic Commons

Reports

On 3-Pushdown Graphs With Large Separators

Galil, Zvi; Kannan, Ravi; Szemeredi, Endre

For an integer s let ZS(n), the s-iterated logarithm function, be defined inductively: [O(n) = n, [8+1(n) = log2(l8(n)) for s 2:: o. We show that for every fixed s and all n large enough, there is an n-vertex 3-pushdown graph whose smallest separator contains at least n(n/[8(n)) vertices.

Subjects

Files

More About This Work

Academic Units
Computer Science
Publisher
Department of Computer Science, Columbia University
Series
Columbia University Computer Science Technical Reports, CUCS-303-87
Published Here
December 2, 2011