{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:01:42Z","timestamp":1787500902598,"version":"build-2736575974"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,1,13]],"date-time":"2015-01-13T00:00:00Z","timestamp":1421107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1147\/09, 671\/13, and 246\/08"],"award-info":[{"award-number":["1147\/09, 671\/13, and 246\/08"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2015,1,13]]},"abstract":"<jats:p>\n                    Motivated by the problem of testing planarity and related properties, we study the problem of designing efficient\n                    <jats:italic>partition oracles<\/jats:italic>\n                    . A\n                    <jats:italic>partition oracle<\/jats:italic>\n                    is a procedure that, given access to the incidence lists representation of a bounded-degree graph\n                    <jats:italic>G<\/jats:italic>\n                    = (\n                    <jats:italic>V,E<\/jats:italic>\n                    ) and a parameter \u03f5, when queried on a vertex\n                    <jats:italic>v<\/jats:italic>\n                    \u2208\n                    <jats:italic>V<\/jats:italic>\n                    , returns the part (subset of vertices) that\n                    <jats:italic>v<\/jats:italic>\n                    belongs to in a partition of all graph vertices. The partition should be such that all parts are small, each part is connected, and if the graph has certain properties, the total number of edges between parts is at most \u03f5 |\n                    <jats:italic>V<\/jats:italic>\n                    |. In this work, we give a partition oracle for graphs with excluded minors whose query complexity is quasi-polynomial in 1\/\u03f5, improving on the result of Hassidim et al. (\n                    <jats:italic>Proceedings of FOCS 2009<\/jats:italic>\n                    ), who gave a partition oracle with query complexity exponential in 1\/\u03f5. This improvement implies corresponding improvements in the complexity of testing planarity and other properties that are characterized by excluded minors as well as sublinear-time approximation algorithms that work under the promise that the graph has an excluded minor.\n                  <\/jats:p>","DOI":"10.1145\/2629508","type":"journal-article","created":{"date-parts":[[2015,1,16]],"date-time":"2015-01-16T09:29:58Z","timestamp":1421400598000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor"],"prefix":"10.1145","volume":"11","author":[{"given":"Reut","family":"Levi","sequence":"first","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dana","family":"Ron","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,1,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100254"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.2748\/tmj\/1178243286"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374433"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00091"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/070681831"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20462"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054106004248"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 15th International Workshop on Randomization and Computation (RANDOM'11)","author":"Edelman Alan","year":"2011","unstructured":"Alan Edelman , Avinatan Hassidim , Huy N. Nguyen , and Krzysztof Onak . 2011 . An efficientpartitioning oracle for bounded-treewidth graphs . In Proceedings of the 15th International Workshop on Randomization and Computation (RANDOM'11) . 530--541. Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, and Krzysztof Onak. 2011. An efficientpartitioning oracle for bounded-treewidth graphs. In Proceedings of the 15th International Workshop on Randomization and Computation (RANDOM'11). 530--541."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2008.01.010"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v37:2"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90086-4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.77"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803896"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01364272"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-39.1.12"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993726"},{"key":"e_1_2_1_22_1","volume-title":"On the Complexity of Learning and Testing Hyperfinite Graphs. Retrieved","author":"Onak Krzysztof","year":"2014","unstructured":"Krzysztof Onak . 2012. On the Complexity of Learning and Testing Hyperfinite Graphs. Retrieved November 5, 2014 from http:\/\/onak.pl\/download\/publications\/Onak-hyperfinite_complexity.pdf. Krzysztof Onak. 2012. On the Complexity of Learning and Testing Hyperfinite Graphs. Retrieved November 5, 2014 from http:\/\/onak.pl\/download\/publications\/Onak-hyperfinite_complexity.pdf."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328911.1328916"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00120-0"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1886521.1886571"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629508","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629508","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:01:18Z","timestamp":1750215678000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629508"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,13]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1,13]]}},"alternative-id":["10.1145\/2629508"],"URL":"https:\/\/doi.org\/10.1145\/2629508","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1,13]]},"assertion":[{"value":"2013-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-01-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}