Applications of a Planar Separator Theorem
SIAM Journal on ComputingPublished 1 August 1980
Richard J. Lipton, Robert E. Tarjan
Citations640
SJR quartileQ1
SJR score1.40
SNIP1.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
Any n-vertex planar graph has the property that it can be divided into components of roughly equal size by removing only $O(\sqrt n )$ vertices. This separator theorem, in combination with a divide-and-conquer strategy, leads to many new complexity results for planar graph problems. This paper describes some of these results.
Keywords
Computer Science
SIAM Journal on Applied MathematicsA Separator Theorem for Planar Graphs
1,338 Citations1979Richard J. Lipton, Robert E. Tarjan
SIAM Journal on Numerical AnalysisNested Dissection of a Regular Finite Element Mesh
1,033 Citations1973Alan D. George
This paper presents an unusual numbering of the mesh (unknowns) and shows that if the authors avoid operating on zeros, the $LDL^T $ factorization of A can be computed using the same standard algorithm in $O(n^3 )$ arithmetic operations.
SIAM Journal on Numerical AnalysisGeneralized Nested Dissection
549 Citations1979Richard J. Lipton, Donald J. Rose +1 more
It is shown that sparse Gaussian elimination is efficient for any class of graphs which have good separator, and conversely that graphs without good separators are not amenable to sparse GaRussian elimination.
Lecture notes in computer scienceGraph-theoretic arguments in low-level complexity
315 Citations1977Leslie G. Valiant
One approach to understanding complexity issues for certain easily computable natural functions is surveyed, and the notion of rigidity does offer for the first time a reduction of relevant computational questions to noncomputional properties.
Information Processing LettersTriangulating a simple polygon
299 Citations1978M. R. Garey, David S. Johnson +2 more
Geometric complexity
264 Citations1975Michael Ian Shamos
An effort is made to recast classical theorems into a useful computational form and analogies are developed between constructibility questions in Euclidean geometry and computability questions in modern computational complexity.
Journal of the ACMOn Time Versus Space
255 Citations1977John E. Hopcroft, Wolfgang J. Paul +1 more
The context-sensitive languages cannot be recognized in linear time by deterministic multitape Turing machines, and are strictly contained in the class of languages recognized by Turing machines of tape complexity.
SIAM Journal on ComputingMultidimensional Searching Problems
249 Citations1976David Dobkin, Richard J. Lipton
Classic binary search is extended to multidimensional search problems and yields efficient algorithms for a number of tasks such as a secondary searching problem of Knuth, region location in planar graphs, and speech recognition.
Journal of Combinatorial Theory Series AOn non-serial dynamic programming
229 Citations1973Umberto Bertelè, Francesco Brioschi
New results in the theory of non-serial dynamic programming are described and their computational relevance is pointed out.
ACM SIGACT NewsThe monotone and planar circuit value problems are log space complete for P
216 Citations1977Leslie M. Goldschlager
It is shown that Ladner's simulation of Turing mac]hines by boolean circuits seems to require an "adequate" set of gates, such as AND and NOT, but the same simulation is possible with monotone circuits using AND and OR gates only.
Computers & GeosciencesComputers and Mathematics with Applications
200 Citations1976Douglas M. Hawkins
The differential transform method (DTM) for solving a class of the system of two-dimensional linear and nonlinear Volterra integro-differential equations of the second kind is developed.
Theory of Computing SystemsSpace bounds for a game on graphs
127 Citations1976Wolfgang J. Paul, Robert E. Tarjan +1 more
It is shown that for each graph withn vertices and maximum in-degreed, there is a pebbling strategy which requires at mostc(d) n/logn pebbles, and this bound is tight to within a constant factor.
Interdisciplinary applied mathematicsIntroduction to Finite Element Analysis
122 Citations2012Weimin Han, B.D. Reddy
On parallelism in turing machines
121 Citations1976Dexter Kozen
A natural characterization of the polynomial time hierarchy of Stockmeyer and Meyer in terms of parallel machines is given, and a generalization of Saviten's result NONDET-L(n)-SPACE ⊆ L(n)2-SPACE is given.
Computers & Mathematics with ApplicationsOn sparse graphs with dense long paths
89 Citations1975P. Erdös, Ronald Graham +1 more
On non-linear lower bounds in computational complexity
68 Citations1975Leslie G. Valiant
It is shown that the graph of any algorithm for any one of a number of arithmetic problems (e.g. polynomial multiplication, discrete Fourier transforms, matrix multiplication) must have properties closely related to concentration networks.
Journal of Computer and System SciencesTape bounds for time-bounded turing machines
49 Citations1972Michael S. Paterson
Let L be a language recognized by a nondeterministic (single-tape) Turing machine of time complexity T(n)>=n^2, and L is also recognized by an deterministic ( single-tapes) Turing Machine of tape complexity T^1^/^2(n).
Communications of the ACMPreserving average proximity in arrays
48 Citations1978Richard A. DeMillo, Stanley C. Eisenstat +1 more
The combinatorial problem of storing arrays as various kinds of list structures is examined, and an elementary proof that arrays cannot be stored as linear lists with bounded loss of proximity is presented.
Journal of the ACMSpace and Time Hierarchies for Classes of Control Structures and Data Structures
47 Citations1976R.J. Lipton, Stanley C. Eisenstat +1 more
Results are presented that establish hierarchies with respect to ≤S.T for (1) data structures, (2) sequential program schemata normal forms, and (3) sequential control structures.
Journal of Graph TheoryOn the independence ratio of a graph
32 Citations1978Michael O. Albertson, Joan P. Hutchinson
It is shown that in a limiting sense these graphs have the same independence ratios as do planar graphs and that every triangulation of a surface of positive genus has a short cycle which does not separate the graph and is non-contractible on that surface.
Nonserial dynamic programming is optimal
8 Citations1977Arnie Rosenthal
It is shown that nonserial dynamic programming is optimal among one class of algorithms for an important class of discrete optimization problems, and the results' strong implications for choosing deterministic, adaptive, and nondeterministic algorithms for the optimization problem.