Motiverade av problemet med att testa planaritet och relaterade egenskaper, studerar vi problemet med att utforma effektiva partitioner orakel. En partition oracle är ett förfarande som, givet tillgång till förekomsten listor representation av en begränsad grad graf G = (V, E) och en parameter, När frågas på en vertex v V, returnerar delen (subset av hörn) som v tillhör i en partition av alla graf hörn. Partitionen bör vara sådan att alla delar är små, varje del är ansluten, och om grafen har vissa egenskaper, det totala antalet kanter mellan delar är som mest. I detta arbete ger vi en partition oracle för grafer med uteslutna minderåriga vars frågekomplexitet är kvasi-polynomial i 1/, förbättra resultatet av Hassidim et al. (Proceedings of FOCS 2009), som gav en partition oracle med frågekomplex exponentiellt i 1/. Denna förbättring innebär motsvarande förbättringar i komplexiteten hos testplanaritet och andra egenskaper som kännetecknas av exkluderade minderåriga samt sublinjärtids approximationsalgoritmer som fungerar under löftet att grafen har en exkluderad minderårig.
Levi och Ron förbättrade senare körtiden för partitionen oracle för mindre slutna klasser av grafer till kvasi-polynomial i 1/ på REF.
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}