Technical reports:
On 3-Pushdown Graphs With Large Separators
Zvi Galil; Ravi Kannan; Endre Szemeredi
Downloads:
- Title:
- On 3-Pushdown Graphs With Large Separators
- Author(s):
-
Galil, Zvi
Kannan, Ravi
Szemeredi, Endre - Date:
- 1987
- Type:
- Technical reports
- Department:
- Computer Science
- Permanent URL:
- http://hdl.handle.net/10022/AC:P:11873
- 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:
- 57