{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T10:38:18Z","timestamp":1780483098394,"version":"3.54.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,10,31]],"date-time":"2016-10-31T00:00:00Z","timestamp":1477872000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000735","name":"University of Cambridge","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000735","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,9]]},"DOI":"10.1007\/s00453-016-0235-7","type":"journal-article","created":{"date-parts":[[2016,10,31]],"date-time":"2016-10-31T18:13:58Z","timestamp":1477937638000},"page":"139-158","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Fixed-Parameter Tractable Distances to Sparse Graph Classes"],"prefix":"10.1007","volume":"79","author":[{"given":"Jannis","family":"Bulian","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anuj","family":"Dawar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,10,31]]},"reference":[{"key":"235_CR1","unstructured":"Adler, I., Grohe, M., Kreutzer, S.: Computing excluded minors. In: SODA \u201908: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM (2008)"},{"issue":"2","key":"235_CR2","doi-asserted-by":"crossref","first-page":"389","DOI":"10.2140\/pjm.1963.13.389","volume":"13","author":"RC Bose","year":"1963","unstructured":"Bose, R.C.: Strongly regular graphs, partial geometries and partially balanced designs. Pac. J. Math. 13(2), 389\u2013419 (1963)","journal-title":"Pac. J. Math."},{"key":"235_CR3","doi-asserted-by":"crossref","unstructured":"Bulian, J., Dawar, A.: Graph isomorphism parameterized by elimination distance to bounded degree. In: Parameterized and Exact Computation\u20149th International Symposium, IPEC: Wroclaw, Poland, September 10\u201312, 2014. Revised Selected Papers 2014, pp. 135\u2013146 (2014)","DOI":"10.1007\/978-3-319-13524-3_12"},{"key":"235_CR4","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(96)00050-6","volume":"58","author":"L Cai","year":"1996","unstructured":"Cai, L.: Fixed-parameter tractability of graph modification problems for hereditary properties. Inf. Process. Lett. 58, 171\u2013176 (1996)","journal-title":"Inf. Process. Lett."},{"key":"235_CR5","doi-asserted-by":"crossref","unstructured":"Dawar, A.: Finite model theory on tame classes of structures, MFCS, Lecture Notes in Computer Science, vol. 4708, pp. 2\u201312. Springer (2007)","DOI":"10.1007\/978-3-540-74456-6_2"},{"issue":"5","key":"235_CR6","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1016\/j.jcss.2009.10.005","volume":"76","author":"A Dawar","year":"2010","unstructured":"Dawar, A.: Homomorphism preservation on quasi-wide classes. J. Comput. Syst. Sci. 76(5), 324\u2013332 (2010)","journal-title":"J. Comput. Syst. Sci."},{"key":"235_CR7","doi-asserted-by":"crossref","unstructured":"Dawar, A., Grohe, M., Kreutzer, S.: Locally excluding a minor. In: Proceedings of 22nd IEEE Symposium on Logic in Computer Science, pp.\u00a0270\u2013279 (2007)","DOI":"10.1109\/LICS.2007.31"},{"key":"235_CR8","volume-title":"Graph Theory","author":"R Diestel","year":"2000","unstructured":"Diestel, R.: Graph Theory. Springer, Berlin (2000)"},{"key":"235_CR9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"2012","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (2012)"},{"key":"235_CR10","volume-title":"Finite Model Theory","author":"H-D Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Springer, Berlin (1999)","edition":"2"},{"issue":"1","key":"235_CR11","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1137\/S0097539799360768","volume":"31","author":"J Flum","year":"2001","unstructured":"Flum, J., Grohe, M.: Fixed-parameter tractability, definability, and model-checking. SIAM J. Comput. 31(1), 113\u2013145 (2001)","journal-title":"SIAM J. Comput."},{"key":"235_CR12","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"235_CR13","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Lokshtanov, D., Misra, N., Saurabh, S.: Planar F-deletion: approximation, kernelization and optimal FPT algorithms. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp.\u00a0470\u2013479 (2012)","DOI":"10.1109\/FOCS.2012.62"},{"key":"235_CR14","doi-asserted-by":"crossref","first-page":"1184","DOI":"10.1145\/504794.504798","volume":"48","author":"M Frick","year":"2001","unstructured":"Frick, M., Grohe, M.: Deciding first-order properties of locally tree-decomposable structures. J. ACM 48, 1184\u20131206 (2001)","journal-title":"J. ACM"},{"key":"235_CR15","doi-asserted-by":"crossref","unstructured":"Gajarsk\u00fd, J., Hlinen\u00fd, P., Obdrz\u00e1lek, J., Ordyniak, S., Reidl, F., Rossmanith, P., Sanchez Villaamil, F., Sikdar, S.: Kernelization using structural parameters on sparse graph classes, Algorithms\u2014ESA 2013\u201421st Annual European Symposium, pp.\u00a0529\u2013540 (2013)","DOI":"10.1007\/978-3-642-40450-4_45"},{"key":"235_CR16","doi-asserted-by":"crossref","unstructured":"Golovach, P.A.: Editing to a graph of given degrees. In: Cygan, M., Heggernes, P. (eds.) Parameterized and Exact Computation, pp. 196\u2013207. Springer, Berlin (2014)","DOI":"10.1007\/978-3-319-13524-3_17"},{"key":"235_CR17","doi-asserted-by":"crossref","unstructured":"Golovach, P.A.: Editing to a connected graph of given degrees. MFCS, vol. 8635, Chapter 28, pp. 324\u2013335 (2014)","DOI":"10.1007\/978-3-662-44465-8_28"},{"key":"235_CR18","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. In: STOC \u201914: Proceedings of the 46th Annual ACM Symposium on Theory of Computing. ACM (2014)","DOI":"10.1145\/2591796.2591851"},{"key":"235_CR19","doi-asserted-by":"crossref","unstructured":"Guo, J., H\u00fcffner, F., Niedermeier, R.: A structural view on parameterizing problems: distance from triviality. In: Downey, R., Fellows, M., Dehne, F. (eds.) Parameterized and Exact Computation, pp. 162\u2013173. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-28639-4_15"},{"key":"235_CR20","volume-title":"A Shorter Model Theory","author":"W Hodges","year":"1997","unstructured":"Hodges, W.: A Shorter Model Theory. Cambridge University Press, Cambridge (1997)"},{"key":"235_CR21","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/s00224-008-9150-x","volume":"47","author":"F H\u00fcffner","year":"2010","unstructured":"H\u00fcffner, F., Komusiewicz, C., Moser, H., Niedermeier, R.: Fixed-parameter algorithms for cluster vertex deletion. Theory Comput. Syst. 47, 196\u2013217 (2010)","journal-title":"Theory Comput. Syst."},{"key":"235_CR22","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/j.tcs.2005.10.008","volume":"351","author":"D Marx","year":"2006","unstructured":"Marx, D.: Parameterized coloring problems on chordal graphs. Theory Comput. Sci. 351, 407\u2013424 (2006)","journal-title":"Theory Comput. Sci."},{"key":"235_CR23","unstructured":"Mathieson, L.: The parameterized complexity of degree constrained editing problems. Ph.D. thesis, Durham University, Durham (2009)"},{"key":"235_CR24","unstructured":"Mathieson, L.: Graph Editing Problems with Extended Regularity Constraints. CoRR abs\/1406.4718cs.CC (2015)"},{"issue":"1","key":"235_CR25","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/j.jcss.2011.02.001","volume":"78","author":"L Mathieson","year":"2012","unstructured":"Mathieson, L., Szeider, S.: Editing graphs to satisfy degree constraints: a parameterized approach. J. Comput. Syst. Sci. 78(1), 179\u2013191 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"235_CR26","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.jda.2008.09.005","volume":"7","author":"H Moser","year":"2009","unstructured":"Moser, H., Thilikos, D.M.: Parameterized complexity of finding regular induced subgraphs. J. Discrete Algorithms 7(2), 181\u2013190 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"235_CR27","doi-asserted-by":"crossref","unstructured":"Nesetril, J., Ossona de Mendez, P.: Sparsity\u2013graphs, structures, and algorithms. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-27875-4"},{"key":"235_CR28","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-27875-4","volume-title":"Sparsity\u2014Graphs, Structures, and Algorithms","author":"J Neset\u0159il","year":"2012","unstructured":"Neset\u0159il, J., de Mendez, P.O.: Sparsity\u2014Graphs, Structures, and Algorithms. Springer, Berlin (2012)"},{"key":"235_CR29","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"235_CR30","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Comb. Theory Ser. B 92, 325\u2013357 (2004)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"235_CR31","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/j.ipl.2007.09.009","volume":"106","author":"IA Stewart","year":"2008","unstructured":"Stewart, I.A.: On the fixed-parameter tractability of parameterized model-checking problems. Inf. Process. Lett. 106(1), 33\u201336 (2008)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0235-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0235-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0235-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,20]],"date-time":"2023-08-20T17:59:03Z","timestamp":1692554343000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0235-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,31]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,9]]}},"alternative-id":["235"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0235-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,31]]}}}