{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T02:51:03Z","timestamp":1774320663588,"version":"3.50.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,1,7]],"date-time":"2019-01-07T00:00:00Z","timestamp":1546819200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["715744"],"award-info":[{"award-number":["715744"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["306992"],"award-info":[{"award-number":["306992"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["267959"],"award-info":[{"award-number":["267959"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005416","name":"Norwegian Research Council","doi-asserted-by":"crossref","award":["NFR MULTIVAL"],"award-info":[{"award-number":["NFR MULTIVAL"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2019,12]]},"DOI":"10.1007\/s00454-018-00054-x","type":"journal-article","created":{"date-parts":[[2019,1,8]],"date-time":"2019-01-08T16:28:08Z","timestamp":1546964888000},"page":"879-911","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs"],"prefix":"10.1007","volume":"62","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6213-8687","authenticated-orcid":false,"given":"Fahad","family":"Panolan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,1,7]]},"reference":[{"key":"54_CR1","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/978-0-387-35608-2_3","volume-title":"Foundations of Information Technology in the Era of Network and Mobile Computing","author":"J Alber","year":"2002","unstructured":"Alber, J., Fiala, J.: Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. In: Baeza-Yates, R., Montanari, U., Santoro, N. (eds.) Foundations of Information Technology in the Era of Network and Mobile Computing, pp. 26\u201337. Springer, New York (2002)"},{"issue":"4","key":"54_CR2","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. Assoc. Comput. Mach. 42(4), 844\u2013856 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1","key":"54_CR3","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. Assoc. Comput. Mach. 41(1), 153\u2013180 (1994)","journal-title":"J. Assoc. Comput. Mach."},{"key":"54_CR4","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.jcss.2017.03.003","volume":"87","author":"A Bj\u00f6rklund","year":"2017","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Narrow sieves for parameterized paths and packings. J. Comput. Syst. Sci. 87, 119\u2013139 (2017)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"54_CR5","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"54_CR6","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015)","journal-title":"Inf. Comput."},{"issue":"8","key":"54_CR7","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"HL Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"54_CR8","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A $c^k n$ 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317\u2013378 (2016)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"54_CR9","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"TM Chan","year":"2003","unstructured":"Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms 46(2), 178\u2013189 (2003)","journal-title":"J. Algorithms"},{"issue":"2","key":"54_CR10","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex cover: further observations and further improvements. J. Algorithms 41(2), 280\u2013301 (2001)","journal-title":"J. Algorithms"},{"issue":"1\u20133","key":"54_CR11","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"BN Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Math. 86(1\u20133), 165\u2013177 (1990)","journal-title":"Discrete Math."},{"issue":"1","key":"54_CR12","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00454-006-1273-8","volume":"37","author":"KL Clarkson","year":"2007","unstructured":"Clarkson, K.L., Varadarajan, K.R.: Improved approximation algorithms for geometric set cover. Discrete Comput. Geom. 37(1), 43\u201358 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"54_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015)"},{"issue":"6","key":"54_CR14","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Fomin, F.V., Hajiaghayi, M., Thilikos, D.M.: Subexponential parameterized algorithms on graphs of bounded genus and $H$-minor-free graphs. J. ACM 52(6), 866\u2013893 (2005)","journal-title":"J. ACM"},{"key":"54_CR15","unstructured":"Demaine, E.D., Hajiaghayi, M.: Bidimensionality: new connections between FPT algorithms and PTASs. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 590\u2013601. ACM-SIAM, New York (2005)"},{"issue":"3","key":"54_CR16","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1093\/comjnl\/bxm033","volume":"51","author":"ED Demaine","year":"2008","unstructured":"Demaine, E.D., Hajiaghayi, M.: The bidimensionality theory and its algorithmic applications. Comput. J. 51(3), 292\u2013302 (2008)","journal-title":"Comput. J."},{"key":"54_CR17","volume-title":"Graph Theory. Graduate Texts in Mathematics","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, New York (2012)","edition":"4"},{"issue":"3","key":"54_CR18","doi-asserted-by":"publisher","first-page":"790","DOI":"10.1007\/s00453-009-9296-1","volume":"58","author":"F Dorn","year":"2010","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: exploiting sphere cut decompositions. Algorithmica 58(3), 790\u2013810 (2010)","journal-title":"Algorithmica"},{"issue":"3","key":"54_CR19","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s00373-011-1026-1","volume":"27","author":"A Dumitrescu","year":"2011","unstructured":"Dumitrescu, A., Pach, J.: Minimum clique partition in unit disk graphs. Graphs Combin. 27(3), 399\u2013411 (2011)","journal-title":"Graphs Combin."},{"key":"54_CR20","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering. In: Proceedings of the 57th Annual Symposium on Foundations of Computer Science (FOCS 2016), pp. 515\u2013524. IEEE Computer Society, Los Alamitos (2016)","DOI":"10.1109\/FOCS.2016.62"},{"issue":"4","key":"54_CR21","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/2886094","volume":"63","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 29 (2016)","journal-title":"J. ACM"},{"key":"54_CR22","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Bidimensionality and EPTAS. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 748\u2013759. SIAM, Philadelphia (2011)","DOI":"10.1137\/1.9781611973082.59"},{"key":"54_CR23","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S.: Bidimensionality and geometric graphs. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pp. 1563\u20131575. SIAM, Philadelphia (2012)","DOI":"10.1137\/1.9781611973099.124"},{"key":"54_CR24","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 503\u2013510. SIAM, Philadelphia (2010)","DOI":"10.1137\/1.9781611973075.43"},{"issue":"12","key":"54_CR25","doi-asserted-by":"publisher","first-page":"1497","DOI":"10.1109\/PROC.1980.11899","volume":"68","author":"WK Hale","year":"1980","unstructured":"Hale, W.K.: Frequency assignment: theory and applications. Proc. IEEE 68(12), 1497\u20131514 (1980)","journal-title":"Proc. IEEE"},{"issue":"1","key":"54_CR26","first-page":"65","volume":"3","author":"S Har-Peled","year":"2012","unstructured":"Har-Peled, S., Lee, M.: Weighted geometric set cover problems revisited. J. Comput. Geom. 3(1), 65\u201385 (2012)","journal-title":"J. Comput. Geom."},{"key":"54_CR27","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Quanrud, K.: Approximation algorithms for polynomial-expansion and low-density graphs. In: Proceedings of the 23rd Annual European Symposium (ESA 2015). Lecture Notes in Computer Science, vol. 9294, pp. 717\u2013728. Springer, Heidelberg (2015)","DOI":"10.1007\/978-3-662-48350-3_60"},{"issue":"1","key":"54_CR28","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32(1), 130\u2013136 (1985)","journal-title":"J. ACM"},{"issue":"6","key":"54_CR29","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16(6), 372\u2013378 (1973)","journal-title":"Commun. ACM"},{"issue":"2","key":"54_CR30","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"HB Hunt III","year":"1998","unstructured":"Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J. Algorithms 26(2), 238\u2013274 (1998)","journal-title":"J. Algorithms"},{"issue":"4","key":"54_CR31","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"54_CR32","unstructured":"Ito, H., Kadoshita, M.: Tractability and intractability of problems on unit disk graphs parameterized by domain area. In: Proceedings of the 9th International Symposium on Operations Research and Its Applications (ISORA\u201910), pp. 120\u2013127 (2010)"},{"key":"54_CR33","doi-asserted-by":"crossref","unstructured":"Jansen, B.: Polynomial kernels for hard problems on disk graphs. In: Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010). Lecture Notes in Computer Science, vol. 6139, pp. 310\u2013321. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-13731-0_30"},{"issue":"4","key":"54_CR34","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1109\/JSAC.1984.1146097","volume":"2","author":"K Kammerlander","year":"1984","unstructured":"Kammerlander, K.: C 900\u2014an advanced mobile radio telephone system with optimum frequency utilization. IEEE J. Sel. Areas Commun. 2(4), 589\u2013597 (1984)","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"54_CR35","doi-asserted-by":"crossref","unstructured":"Koutis, I.: Faster algebraic algorithms for path and packing problems. In: Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008). Lecture Notes in Computer Science, vol. 5125, pp. 575\u2013586. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-70575-8_47"},{"issue":"1","key":"54_CR36","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1145\/2742544","volume":"59","author":"I Koutis","year":"2016","unstructured":"Koutis, I., Williams, R.: Algebraic fingerprints for faster algorithms. Commun. ACM 59(1), 98\u2013105 (2016)","journal-title":"Commun. ACM"},{"key":"54_CR37","doi-asserted-by":"crossref","unstructured":"Marx, D.: Efficient approximation schemes for geometric problems? In: Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005). Lecture Notes in Computer Science, vol. 3669, pp. 448\u2013459. Springer, Berlin (2005)","DOI":"10.1007\/11561071_41"},{"key":"54_CR38","doi-asserted-by":"crossref","unstructured":"Mustafa, N.H., Raman, R., Ray, S.: Settling the APX-hardness status for geometric set cover. In: Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2014), pp. 541\u2013550. IEEE Computer Society, Philadelphia (2014)","DOI":"10.1109\/FOCS.2014.64"},{"key":"54_CR39","unstructured":"Smith, W.D., Wormald, N.C.: Geometric separator theorems & applications. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 1998), pp. 232\u2013243. IEEE Computer Society, Philadelphia (1998)"},{"issue":"2","key":"54_CR40","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/1721837.1721848","volume":"6","author":"S Thomass\u00e9","year":"2010","unstructured":"Thomass\u00e9, S.: A $4k^2$ kernel for feedback vertex set. ACM Trans. Algorithms 6(2), 32 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"6","key":"54_CR41","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0020-0190(88)90174-3","volume":"28","author":"D Wang","year":"1988","unstructured":"Wang, D., Kuo, Y.-S.: A study on two geometric location problems. Inf. Process. Lett. 28(6), 281\u2013286 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"54_CR42","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ipl.2008.11.004","volume":"109","author":"R Williams","year":"2009","unstructured":"Williams, R.: Finding paths of length $k$ in ${O}^*(2^k)$ time. Inf. Process. Lett. 109(6), 315\u2013318 (2009)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"54_CR43","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1109\/JSAC.1984.1146082","volume":"2","author":"YS Yeh","year":"1984","unstructured":"Yeh, Y.S., Wilson, J., Schwartz, S.: Outage probability in mobile telephony with directive antennas and macrodiversity. IEEE J. Sel. Areas Commun. 2(4), 507\u2013511 (1984)","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"54_CR44","doi-asserted-by":"crossref","unstructured":"Zehavi, M.: Mixing color coding-related techniques. In: Proceedings of the 23rd Annual European Symposium on Algorithms (ESA 2015). Lecture Notes in Computer Science, vol. 9294, pp. 1037\u20131049. Springer, Heidelberg (2013)","DOI":"10.1007\/978-3-662-48350-3_86"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-018-00054-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-018-00054-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-018-00054-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,6]],"date-time":"2020-01-06T19:23:03Z","timestamp":1578338583000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-018-00054-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,7]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["54"],"URL":"https:\/\/doi.org\/10.1007\/s00454-018-00054-x","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,7]]},"assertion":[{"value":"11 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 November 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 December 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}