On 3-Pushdown Graphs With Large Separators
- On 3-Pushdown Graphs With Large Separators
- Galil, Zvi
- Computer Science
- Persistent URL:
- Columbia University Computer Science Technical Reports
- Part Number:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- 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.
- Computer science
- Item views
text | xml
- Suggested Citation:
- Zvi Galil, Ravi Kannan, Endre Szemeredi, 1987, On 3-Pushdown Graphs With Large Separators, Columbia University Academic Commons, https://doi.org/10.7916/D8WQ0BVP.