Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Planar_separator_theorem> ?p ?o. }
Showing items 1 to 45 of
45
with 100 items per page.
- Planar_separator_theorem abstract "In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of O(√n) vertices from an n-vertex graph (where the O invokes big O notation) can partition the graph into disjoint subgraphs each of which has at most 2n/3 vertices.A weaker form of the separator theorem with O(√n log n) vertices in the separator instead of O(√n) was originally proven by Ungar (1951), and the form with the tight asymptotic bound on the separator size was first proven by Lipton & Tarjan (1979). Since their work, the separator theorem has been reproven in several different ways, the constant in the O(√n) term of the theorem has been improved, and it has been extended to certain classes of nonplanar graphs.Repeated application of the separator theorem produces a separator hierarchy which may take the form of either a tree decomposition or a branch-decomposition of the graph. Separator hierarchies may be used to devise efficient divide and conquer algorithms for planar graphs, and dynamic programming on these hierarchies can be used to devise exponential time and fixed-parameter tractable algorithms for solving NP-hard optimization problems on these graphs. Separator hierarchies may also be used in nested dissection, an efficient variant of Gaussian elimination for solving sparse systems of linear equations arising from finite element methods.".
- Planar_separator_theorem thumbnail Grid_separator.svg?width=300.
- Planar_separator_theorem wikiPageExternalLink mincut.ps.
- Planar_separator_theorem wikiPageExternalLink 20.
- Planar_separator_theorem wikiPageExternalLink citation.cfm?id=314613.314632.
- Planar_separator_theorem wikiPageExternalLink citation.cfm?id=314625.
- Planar_separator_theorem wikiPageExternalLink 1982-12.pdf.
- Planar_separator_theorem wikiPageExternalLink purl?GDZPPN002153998.
- Planar_separator_theorem wikiPageExternalLink planar.pdf.
- Planar_separator_theorem wikiPageExternalLink GaMi90.pdf.
- Planar_separator_theorem wikiPageExternalLink GrMiTe94.pdf.
- Planar_separator_theorem wikiPageExternalLink Mi87.pdf.
- Planar_separator_theorem wikiPageExternalLink BBK03.pdf.
- Planar_separator_theorem wikiPageExternalLink planarSep.pdf.
- Planar_separator_theorem wikiPageExternalLink EppMilTen-FI-95.ps.gz.
- Planar_separator_theorem wikiPageExternalLink 0427-11.pdf.
- Planar_separator_theorem wikiPageExternalLink sep.pdf.
- Planar_separator_theorem wikiPageExternalLink 116universal.pdf.
- Planar_separator_theorem wikiPageExternalLink 117separatorthms.pdf.
- Planar_separator_theorem wikiPageExternalLink 1976-26.pdf.
- Planar_separator_theorem wikiPageID "18978005".
- Planar_separator_theorem wikiPageRevisionID "593424338".
- Planar_separator_theorem hasPhotoCollection Planar_separator_theorem.
- Planar_separator_theorem subject Category:Planar_graphs.
- Planar_separator_theorem subject Category:Theorems_in_graph_theory.
- Planar_separator_theorem type Abstraction100002137.
- Planar_separator_theorem type Communication100033020.
- Planar_separator_theorem type Graph107000195.
- Planar_separator_theorem type Message106598915.
- Planar_separator_theorem type PlanarGraphs.
- Planar_separator_theorem type Proposition106750804.
- Planar_separator_theorem type Statement106722453.
- Planar_separator_theorem type Theorem106752293.
- Planar_separator_theorem type TheoremsInDiscreteMathematics.
- Planar_separator_theorem type VisualCommunication106873252.
- Planar_separator_theorem comment "In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices.".
- Planar_separator_theorem label "Planar separator theorem".
- Planar_separator_theorem sameAs Θεώρημα_διαχωρισμού_του_επιπέδου.
- Planar_separator_theorem sameAs m.04jbn34.
- Planar_separator_theorem sameAs Q7200963.
- Planar_separator_theorem sameAs Q7200963.
- Planar_separator_theorem sameAs Planar_separator_theorem.
- Planar_separator_theorem wasDerivedFrom Planar_separator_theorem?oldid=593424338.
- Planar_separator_theorem depiction Grid_separator.svg.
- Planar_separator_theorem isPrimaryTopicOf Planar_separator_theorem.
