On 3-pushdown graphs with large separators

DOI10.1007/BF02122679MaRDI QIDQ2277467zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Zvi Galil, R. Kannan, Endre Szemerédi

Publication date 1989

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02122679

zbMATH Keywords

3-pushdown graphseparator

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines
• A pumping lemma for pushdown graphs of any level
• Planar Separators
• scientific article; zbMATH DE number 16297
• scientific article; zbMATH DE number 867693

Cites work

• Applications of a Planar Separator Theorem
• Characterizations of outerplanar graphs
• Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Graph-theoretic properties in computational complexity
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines
• On Time Versus Space
• Unraveling k-page graphs

Cited in

(5)

• On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines
• Stack-number is not bounded by queue-number
• On exteriority notions in book embeddings and treewidth
• Layouts of Expander Graphs
• Characterisations and examples of graph classes with bounded expansion

This page was built for publication: On 3-pushdown graphs with large separators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277467)