Matches in DBpedia 2016-04 for { <http://wikidata.dbpedia.org/resource/Q7200963> ?p ?o }
- Q7200963 subject Q7007191.
- Q7200963 subject Q7494515.
- Q7200963 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.Bidimensionality theory of Demaine, Fomin, Hajiaghayi, and Thilikos generalizes and greatly expands the applicability of the separator theorem for a vast set of minimization problems on planar graphs and more generally graphs excluding a fixed minor.".
- Q7200963 thumbnail Grid_separator.svg?width=300.
- Q7200963 wikiPageExternalLink mincut.ps.
- Q7200963 wikiPageExternalLink citation.cfm?id=314613.314632.
- Q7200963 wikiPageExternalLink citation.cfm?id=314625.
- Q7200963 wikiPageExternalLink 1982-12.pdf.
- Q7200963 wikiPageExternalLink purl?GDZPPN002153998.
- Q7200963 wikiPageExternalLink BBK03.pdf.
- Q7200963 wikiPageExternalLink EppMilTen-FI-95.ps.gz.
- Q7200963 wikiPageExternalLink 0427-11.pdf.
- Q7200963 wikiPageExternalLink 1976-26.pdf.
- Q7200963 wikiPageExternalLink 20.
- Q7200963 wikiPageExternalLink planar.pdf.
- Q7200963 wikiPageExternalLink GaMi90.pdf.
- Q7200963 wikiPageExternalLink GrMiTe94.pdf.
- Q7200963 wikiPageExternalLink Mi87.pdf.
- Q7200963 wikiPageExternalLink planarSep.pdf.
- Q7200963 wikiPageExternalLink sep.pdf.
- Q7200963 wikiPageExternalLink 116universal.pdf.
- Q7200963 wikiPageExternalLink 117separatorthms.pdf.
- Q7200963 wikiPageWikiLink Q1050404.
- Q7200963 wikiPageWikiLink Q1058754.
- Q7200963 wikiPageWikiLink Q1060343.
- Q7200963 wikiPageWikiLink Q1064349.
- Q7200963 wikiPageWikiLink Q10884.
- Q7200963 wikiPageWikiLink Q11197.
- Q7200963 wikiPageWikiLink Q11203.
- Q7200963 wikiPageWikiLink Q1137554.
- Q7200963 wikiPageWikiLink Q12507.
- Q7200963 wikiPageWikiLink Q12916.
- Q7200963 wikiPageWikiLink Q1306887.
- Q7200963 wikiPageWikiLink Q131222.
- Q7200963 wikiPageWikiLink Q131476.
- Q7200963 wikiPageWikiLink Q1368270.
- Q7200963 wikiPageWikiLink Q146657.
- Q7200963 wikiPageWikiLink Q14715698.
- Q7200963 wikiPageWikiLink Q1570441.
- Q7200963 wikiPageWikiLink Q1626444.
- Q7200963 wikiPageWikiLink Q166507.
- Q7200963 wikiPageWikiLink Q17016378.
- Q7200963 wikiPageWikiLink Q1709878.
- Q7200963 wikiPageWikiLink Q175263.
- Q7200963 wikiPageWikiLink Q1759539.
- Q7200963 wikiPageWikiLink Q1764144.
- Q7200963 wikiPageWikiLink Q179976.
- Q7200963 wikiPageWikiLink Q180953.
- Q7200963 wikiPageWikiLink Q184410.
- Q7200963 wikiPageWikiLink Q185148.
- Q7200963 wikiPageWikiLink Q190524.
- Q7200963 wikiPageWikiLink Q215206.
- Q7200963 wikiPageWikiLink Q21662943.
- Q7200963 wikiPageWikiLink Q220184.
- Q7200963 wikiPageWikiLink Q226995.
- Q7200963 wikiPageWikiLink Q2294516.
- Q7200963 wikiPageWikiLink Q230655.
- Q7200963 wikiPageWikiLink Q2321565.
- Q7200963 wikiPageWikiLink Q2393193.
- Q7200963 wikiPageWikiLink Q245595.
- Q7200963 wikiPageWikiLink Q2493.
- Q7200963 wikiPageWikiLink Q2589168.
- Q7200963 wikiPageWikiLink Q260928.
- Q7200963 wikiPageWikiLink Q2658.
- Q7200963 wikiPageWikiLink Q269878.
- Q7200963 wikiPageWikiLink Q272735.
- Q7200963 wikiPageWikiLink Q273037.
- Q7200963 wikiPageWikiLink Q2855103.
- Q7200963 wikiPageWikiLink Q2915204.
- Q7200963 wikiPageWikiLink Q2976589.
- Q7200963 wikiPageWikiLink Q303100.
- Q7200963 wikiPageWikiLink Q3045660.
- Q7200963 wikiPageWikiLink Q3085841.
- Q7200963 wikiPageWikiLink Q322212.
- Q7200963 wikiPageWikiLink Q325904.
- Q7200963 wikiPageWikiLink Q339011.
- Q7200963 wikiPageWikiLink Q33971.
- Q7200963 wikiPageWikiLink Q341835.
- Q7200963 wikiPageWikiLink Q3531564.
- Q7200963 wikiPageWikiLink Q380172.
- Q7200963 wikiPageWikiLink Q380679.
- Q7200963 wikiPageWikiLink Q383444.
- Q7200963 wikiPageWikiLink Q3851477.
- Q7200963 wikiPageWikiLink Q4129097.
- Q7200963 wikiPageWikiLink Q44337.
- Q7200963 wikiPageWikiLink Q462095.
- Q7200963 wikiPageWikiLink Q4904170.
- Q7200963 wikiPageWikiLink Q491370.
- Q7200963 wikiPageWikiLink Q4956329.
- Q7200963 wikiPageWikiLink Q5060048.
- Q7200963 wikiPageWikiLink Q5067368.
- Q7200963 wikiPageWikiLink Q5121501.
- Q7200963 wikiPageWikiLink Q5121504.
- Q7200963 wikiPageWikiLink Q515375.
- Q7200963 wikiPageWikiLink Q518131.
- Q7200963 wikiPageWikiLink Q5319002.
- Q7200963 wikiPageWikiLink Q5467387.
- Q7200963 wikiPageWikiLink Q547823.
- Q7200963 wikiPageWikiLink Q5597085.
- Q7200963 wikiPageWikiLink Q573901.