Home

On 3-Pushdown Graphs With Large Separators

Zvi Galil; Ravi Kannan; Endre Szemeredi

Title:
On 3-Pushdown Graphs With Large Separators
Author(s):
Galil, Zvi
Kannan, Ravi
Szemeredi, Endre
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
Series:
Columbia University Computer Science Technical Reports
Part Number:
CUCS-303-87
Publisher:
Department of Computer Science, Columbia University
Publisher Location:
New York
Abstract:
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.
Subject(s):
Computer science
Item views:
87
Metadata:
text | xml

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services | Terms of Use