On nontrivial separators for \(k\)-page graphs and simulations by nondeterministic one-tape Turing machines

DOI10.1016/0022-0000(89)90036-6zbMath0676.68019OpenAlexW4253594684WikidataQ29400454 ScholiaQ29400454MaRDI QIDQ1122982

Zvi Galil, Endre Szemerédi, Ravindran Kannan

Publication date: 1989

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(89)90036-6

zbMATH Keywords

\(k\)-page graphs\(k\)-pushdown graphsimulation of two-tape nondeterministic Turing machines by one-tape nondeterministic Turing machinessublinear separators

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Characterisations and examples of graph classes with bounded expansion, The hardest halfspace, Layouts of Expander Graphs, On 3-pushdown graphs with large separators, On exteriority notions in book embeddings and treewidth, Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design

Cites Work

• Unnamed Item
• Graph-theoretic properties in computational complexity
• Characterizations of outerplanar graphs
• Unraveling k-page graphs
• Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
• Applications of a Planar Separator Theorem
• On Time Versus Space
• Quasi-realtime languages