Introduction tw t P m c in planar graphs Algorithm Conclusion
38
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
38
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
1/12 Introduction tw ≤ t P.m.c. in planar graphs Algorithm Conclusion Exact algorithm for the Maximum Induced Planar Subgraph Problem Fedor Fomin Ioan Todinca Yngve Villanger University of Bergen, Universite d'Orleans Workshop on Graph Decompositions, CIRM, October 19th, 2010
Voir
- introduction tw ≤
- finite combinatorial
- exact algorithms
- combinatorial results
- planar graphs
- algorithm conclusion
- problems can
- hard problems
Exact algorithm for the Maximum Induced Planar Subgraph Problem
Fedor Fomin Ioan Todinca
Yngve Villanger
Workshop on Graph Decompositions, CIRM, October 19th, 2010
UniversityofBergen,Universit´ed’Orle´ans
1.[Fomin, Villanger, STACS 2010]: anO(1.73601n∙nt+3) algorithm for theMax Induced Subgraph of Theewidth≤t 2.[Robertson, Seymour 1986; Fomin, Thilikos 2006]: planar graphs have treewidthO(√n)
Ingredients: 1.[Fomin
Theorem There is an O(1.73601n)algorithm for theMax Induced Planar Subgraphproblem.
itgnvereirhtpmtugether
Outline of the result
ythingto
1.[Fomin, Villanger, STACS 2010]: anO(1.73601n∙nt+3) algorithm for theMax Induced Subgraph of Theewidth≤t 2.[Robertson, Seymour 1986; Fomin, Thilikos 2006]: planar graphs have treewidthO(√n) 3.Combinatorial results onminimal triangulationsandpotential maximal cliquesof planar graphs.
Ingredients: 1.[Fomin
teehr
Theorem There is an O(1.73601n)algorithm for theMax Induced Planar Subgraphproblem.
Outline of the result
thingtogingeveryI2tnorudtcoitn≤w2/1isnocnulCohmitorlgsAphragranalpni.c.m.Pt
