×
Lipton, Richard J.; Tarjan, Robert Endre

Applications of a planar separator theorem. (English) Zbl 0456.68077

SIAM J. Comput. 9, 615-627 (1980).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0456.68077

Cited in 7 Reviews
Cited in 183 Documents

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q25 Analysis of algorithms and problem complexity

Keywords:

algorithm; Boolean circuit complexity; divide-and-conquer; graph embedding; matching; maximum independent set; pebbling; planar graphs; space-time tradeoffs
Cite Review PDF
Full Text: DOI