{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:28:12Z","timestamp":1759638492366,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","license":[{"start":{"date-parts":[[2014,5,31]],"date-time":"2014-05-31T00:00:00Z","timestamp":1401494400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1016799, CCF-1319811"],"award-info":[{"award-number":["CCF-1016799, CCF-1319811"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007063","name":"Mellon College of Science, Carnegie Mellon University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007063","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["303809"],"award-info":[{"award-number":["303809"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["523\/12"],"award-info":[{"award-number":["523\/12"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2014,5,31]]},"DOI":"10.1145\/2591796.2591849","type":"proceedings-article","created":{"date-parts":[[2015,10,1]],"date-time":"2015-10-01T12:01:58Z","timestamp":1443700918000},"page":"79-88","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Cops, robbers, and threatening skeletons"],"prefix":"10.1145","author":[{"given":"Ittai","family":"Abraham","sequence":"first","affiliation":[{"name":"Microsoft Research SVC"}]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[{"name":"LaBRI - University of Bordeaux, Bordeaux, France"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]},{"given":"Ofer","family":"Neiman","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer-Sheva, Israel"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[{"name":"Microsoft Research SVC"}]}],"member":"320","published-online":{"date-parts":[[2014,5,31]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9283-6"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1990-1065053-0"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90026-2"},{"key":"e_1_3_2_2_4_1","first-page":"1079","volume-title":"Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Archer Aaron","year":"2004","unstructured":"Aaron Archer , Jittat Fakcharoenphol , Chris Harrelson , Robert Krauthgamer , Kunal Talwar , and \u00c9va Tardos . Approximate classification via earthmover metrics . In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1079 -- 1087 , New York , 2004 . ACM. Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, and \u00c9va Tardos. Approximate classification via earthmover metrics. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1079--1087, New York, 2004. ACM."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4227"},{"key":"e_1_3_2_2_6_1","first-page":"184","volume-title":"Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS '96","author":"Bartal Y.","unstructured":"Y. Bartal . Probabilistic approximation of metric spaces and its algorithmic applications . In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS '96 , pages 184 --, Washington, DC, USA, 1996. IEEE Computer Society. Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS '96, pages 184--, Washington, DC, USA, 1996. IEEE Computer Society."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706591.1706593"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2010.04.007"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281112"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701395978"},{"key":"e_1_3_2_2_11_1","series-title":"Graduate Texts in Mathematics","volume-title":"Graph theory","author":"Diestel Reinhard","year":"2000","unstructured":"Reinhard Diestel . Graph theory , volume 173 of Graduate Texts in Mathematics . Springer-Verlag , New York , second edition, 2000 . Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 2000."},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45198-3_4"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946308"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247069.1247107"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.69"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167261"},{"key":"e_1_3_2_2_19_1","volume-title":"February","author":"Lee James R.","year":"2013","unstructured":"James R. Lee . Open question recap , February 2013 . http:\/\/tcsmath.wordpress.com\/2013\/02\/25\/openquestion-recap\/. James R. Lee. Open question recap, February 2013. http:\/\/tcsmath.wordpress.com\/2013\/02\/25\/openquestion-recap\/."},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214078"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00222-004-0400-5"},{"key":"e_1_3_2_2_22_1","first-page":"193","volume-title":"SODA","author":"James","year":"2010","unstructured":"James R. Lee and Anastasios Sidiropoulos. Genus and the geometry of the cut graph . In SODA , pages 193 -- 201 , 2010 . James R. Lee and Anastasios Sidiropoulos. Genus and the geometry of the cut graph. In SODA, pages 193--201, 2010."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303516"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/581165"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/314464.314625"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780609"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/304893.304983"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00042-X"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.23"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.15"}],"event":{"name":"STOC '14: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"New York New York","acronym":"STOC '14"},"container-title":["Proceedings of the forty-sixth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2591796.2591849","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2591796.2591849","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:55:45Z","timestamp":1750229745000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2591796.2591849"}},"subtitle":["padded decomposition for minor-free graphs"],"short-title":[],"issued":{"date-parts":[[2014,5,31]]},"references-count":30,"alternative-id":["10.1145\/2591796.2591849","10.1145\/2591796"],"URL":"https:\/\/doi.org\/10.1145\/2591796.2591849","relation":{},"subject":[],"published":{"date-parts":[[2014,5,31]]},"assertion":[{"value":"2014-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}