×

On 3-pushdown graphs with large separators. (English) Zbl 0726.05042

Summary: For an integer s let \(l^ s(n)\), the s-iterated logarithm function, be defined inductively: \(l^ 0(n)=n\), \(l^{s+1}(n)=\log_ 2(l^ s(n))\) for \(s\geq 0\). 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 \(\Omega (n/l^ s(n))\) vertices.

MSC:

05C35 Extremal problems in graph theory
68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] B. S.Baker (1983), Approximation algorithms for NP-complete problems, inProc. 24th IEEE Annual Symp. on the Foundations of Computer Science, 265–273.
[2] B. Bollobás (1978),Extremal Graph Theory, Prentice Hall, London, New York, pp. xx.
[3] B. Bollobás (1985),Random Graphs, Prentice Hall, London, New York, pp. 11. · Zbl 0567.05042
[4] J.Buss and O.Shor (1984), On the pagenumber of planar graphs, inProc. 16th ACM Symp. on the Theory of Computing, 98–101.
[5] F.Chung, F. T.Leighton and A.Rosenberg (1984),Embedding graphs in books: A layout problem with applications to VLSI design, manuscript. · Zbl 0617.68062
[6] Z.Galil, R.Kannan and E.Szemerédi, On nontrivial separators fork-page graphs and simulations by nondeterministic one-tape Turing machines, to appear inJCSS. · Zbl 0676.68019
[7] L.Heath (1984), Embedding planar graphs in seven pages, inProc. 25th IEEE Symp. on the Foundations of Computer Science, 74–83.
[8] J. Hopcroft, W. Paul andL. Valiant (1977), On time versus space,J. Assoc. Comput. Math. 24, 332–337. · Zbl 0358.68082
[9] R. Kannan (1985), Unravelingk page graphs,Info. & Control 66, 1–5. · Zbl 0584.05055 · doi:10.1016/S0019-9958(85)80008-5
[10] R. J. Lipton andR. E. Tarjan (1980), Applications of a planar graph separator theorem,SIAM J. Comput. 9, No. 3, 615–627. · Zbl 0456.68077 · doi:10.1137/0209046
[11] W. Maass (1985), Combinatorial lower bound arguments for deterministic and non-deterministic Turning machines,Trans. Amer. Math. Soc. 292, No.2, 675–693. · Zbl 0608.03013 · doi:10.1090/S0002-9947-1985-0808746-4
[12] W. I.Paul, N.Pippenger, E.Szemerédi and W. T.Trotter (1983), On determinism versus non-determinism, inProc. 24th Symp. on the Foundations of Computer Science, 429–238.
[13] A. L. Rosenberg (1983), The Diogenes approach to testable fault-tolerant arrays of processors,IEEE Trans. Comput. C-32, pp. 902–910. · doi:10.1109/TC.1983.1676134
[14] M. M. Syslo (1979), Characterisations of outerplanar graphs,Discrete Math. 26, 47–53. · Zbl 0401.05040 · doi:10.1016/0012-365X(79)90060-8
[15] L. G. Valiant, (1976), Graph-theoretic properties in computational complexity,J. Comput. System Sci. 13, 278–285. · Zbl 0354.68071 · doi:10.1016/S0022-0000(76)80041-4
[16] M.Yannakakis (1986), Four pages are necessary and sufficient, inProc. 18th ACM Symp. on the Theory of Computing, 104–108.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.