Applications of a Planar Separator Theorem.

reportActive / Technical Report | Accession Number: ADA048787 | Open PDF

Abstract:

Any n-vertex planar graph has the property that it can be divided into components of roughly equal size by removing only Osquare root of 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. Author

Author(s):
Lipton, Richard J. ; Tarjan, Robert E.
Author Organization(s):
STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Descriptive Note:
Technical rept.,
Pagination:
0036

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
STAN-CS-77-628
Contract/Grant Number(s):
N00014-76-C-0688, NSF-MCS-75-22870
 Subject Terms
Joint Capability Areas:
JCA_1_Force Support; JCA_1.2_Force Preparation; JCA_5_Command and Control; JCA_1.2.3_Educating; JCA_5.3_Planning; JCA_1.3_Human Capital Management
Modernization Areas:
Quantum Science and Computing
Communities of Interest:
Air Platforms
Descriptor(s):
*PROBLEM SOLVING, ALGORITHMS, COMPUTATIONS, GRAPHS, PLANAR STRUCTURES, COMPUTER APPLICATIONS, CIRCUITS, DYNAMIC PROGRAMMING, THEOREMS, SEPARATORS
Field(s)/Group(s):
Theoretical Mathematics
Keyword(s):
Boolean circuits
Report Date:
1977 Oct 01