{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T18:36:39Z","timestamp":1770921399505,"version":"3.50.1"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032178008","type":"print"},{"value":"9783032178015","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-17801-5_15","type":"book-chapter","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:07Z","timestamp":1770918787000},"page":"203-215","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Practical Algorithm for\u00a03-Admissibility"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-3550-1727","authenticated-orcid":false,"given":"Christine","family":"Awofeso","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0007-0752-0526","authenticated-orcid":false,"given":"Patrick","family":"Greaves","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5406-8121","authenticated-orcid":false,"given":"Oded","family":"Lachish","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2354-3003","authenticated-orcid":false,"given":"Felix","family":"Reidl","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"key":"15_CR1","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12, 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"key":"15_CR2","unstructured":"Awofeso, C., \u00a0Greaves, P., \u00a0Lachish, O., Reidl, F.: A practical algorithm for 2-admissibility. In: Mutzel, P., and Prezza, N. (eds.) 23rd International Symposium on Experimental Algorithms, SEA 2025, July 22\u201324, Venice, Italy, vol.\u00a0338 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2025, pp.\u00a03:1\u20133:19 (2025)"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput., 85, 12\u201375 (1990)","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Demaine, E., Hajiaghayi, M., Kawarabayashi, K.: Algorithmic graph minor theory: Decomposition, approximation, and coloring. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201905), pp.\u00a0637\u2013646 (2025)","DOI":"10.1109\/SFCS.2005.14"},{"key":"15_CR5","unstructured":"Drange, P.G., Greaves, P., Muzi, I., Reidl, F.: Computing Complexity Measures of Degenerate Graphs. In: 18th International Symposium on Parameterized and Exact Computation (IPEC 2023), vol.\u00a0285 of Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, pp.\u00a014:1\u201314:21 (2023)"},{"key":"15_CR6","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1016\/j.ejc.2012.12.004","volume":"34","author":"Z Dvo\u0159\u00e1k","year":"2013","unstructured":"Dvo\u0159\u00e1k, Z.: Constant-factor approximation of the domination number in sparse graphs. Eur. J. Comb. 34, 833\u2013840 (2013)","journal-title":"Eur. J. Comb."},{"key":"15_CR7","unstructured":"Dvo\u0159\u00e1k, Z.: Approximation metatheorems for classes with bounded expansion. In: 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022, June 27-29, 2022, T\u00f3rshavn, Faroe Islands, vol.\u00a0227 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fur Informatik, pp.\u00a022:1\u201322:17 (2022)"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1l, D., Thomas, R.: Deciding first-order properties for sparse graphs. In: IEEE 51st Annual Symposium on Foundations of Computer Science. IEEE 2010, 133\u2013142 (2010)","DOI":"10.1109\/FOCS.2010.20"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1l, D., Thomas, R.: Testing first-order properties for subclasses of sparse graphs. J. ACM, 60, 36:1\u201336:24 (2013)","DOI":"10.1145\/2499483"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Nadara, W., Pilipczuk, M., Rabinovich, R., Reidl, F., Siebertz, S.: Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness. ACM J. Exp. Algorithmics, 24, 2.6:1\u20132.6:34 (2019)","DOI":"10.1145\/3368630"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Grad and classes with bounded expansion II. Algorithmic aspects. Eur. J. Comb., 29, 777\u2013791 (2008)","DOI":"10.1016\/j.ejc.2006.07.014"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Paul-Pena, D., Seshadhri, C.: A dichotomy hierarchy for linear time subgraph counting in bounded degeneracy graphs. In: Azar, Y., Panigrahi, D. (eds.) Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12\u201315, 2025, SIAM, pp.\u00a048\u201387 (2025)","DOI":"10.1137\/1.9781611978322.2"},{"key":"15_CR13","first-page":"85","volume-title":"Recent Advances in Algorithms and Combinatorics","author":"BA Reed","year":"2003","unstructured":"Reed, B.A.: Algorithmic Aspects of Tree Width. In: Reed, B.A., Sales, C.L. (eds.) Recent Advances in Algorithms and Combinatorics, pp. 85\u2013107. Springer, New York, NY (2003)"},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"2318","DOI":"10.1007\/s00453-023-01096-1","volume":"85","author":"F Reidl","year":"2023","unstructured":"Reidl, F., Sullivan, B.D.: A color-avoiding approach to subgraph counting in bounded expansion classes. Algorithmica 85, 2318\u20132347 (2023)","journal-title":"Algorithmica"},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1017\/S0960129500070079","volume":"6","author":"D Seese","year":"1996","unstructured":"Seese, D.: Linear time computable problems and first-order descriptions. Math. Struct. Comput. Sci. 6, 505\u2013526 (1996)","journal-title":"Math. Struct. Comput. Sci."},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Siebertz, S.: On the generalized coloring numbers. arXiv preprint arXiv:2501.08698 (2025)","DOI":"10.1016\/j.cosrev.2025.100855"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2026: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-17801-5_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:11Z","timestamp":1770918791000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-17801-5_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032178008","9783032178015"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-17801-5_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Krakow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 February 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 February 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sofsem.uj.edu.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}