{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T19:02:37Z","timestamp":1743015757560,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030967307"},{"type":"electronic","value":"9783030967314"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-030-96731-4_2","type":"book-chapter","created":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T00:03:49Z","timestamp":1647389029000},"page":"15-25","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["From the W-hierarchy to XNLP"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9297-3330","authenticated-orcid":false,"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,16]]},"reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0168-0072(94)00034-Z","volume":"73","author":"KA Abrahamson","year":"1995","unstructured":"Abrahamson, K.A., Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness IV: On completeness for $$W[P]$$ and PSPACE analogues. Ann. Pure Appl. Logic 73, 235\u2013276 (1995)","journal-title":"Ann. Pure Appl. Logic"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Abrahamson, K.R., Ellis, J.A., Fellows, M.R., Mata, M.E.: On the complexity of fixed-parameter problems. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science, FOCS 1989, pp. 210\u2013215 (1989)","DOI":"10.1109\/SFCS.1989.63480"},{"issue":"4","key":"2_CR3","first-page":"576","volume":"8","author":"A Adachi","year":"1979","unstructured":"Adachi, A., Iwata, S., Kasai, T.: Classes of pebble games and complete problems. SIAM J. Comput. 8(4), 576\u2013586 (1979)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"2_CR4","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1145\/62.322433","volume":"31","author":"A Adachi","year":"1984","unstructured":"Adachi, A., Iwata, S., Kasai, T.: Some combinatorial game problems require $${\\Omega (n^k)}$$ time. J. ACM 31(2), 361\u2013376 (1984)","journal-title":"J. ACM"},{"key":"2_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-030-86838-3_2","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"HL Bodlaender","year":"2021","unstructured":"Bodlaender, H.L.: Parameterized complexity of Bandwidth of caterpillars and Weighted Path Emulation. In: Kowalik, \u0141, Pilipczuk, M., Rz\u0105\u017cewski, P. (eds.) WG 2021. LNCS, vol. 12911, pp. 15\u201327. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-86838-3_2"},{"key":"2_CR6","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, 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fellows, M.R., Hallett, M.: Beyond NP-completeness for problems of bounded width: Hardness for the $$W$$ hierarchy. In: Proceedings of the 26th Annual Symposium on Theory of Computing, STOC 1994, pp. 449\u2013458. ACM Press, New York (1994)","DOI":"10.1145\/195058.195229"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Groenland, C., Nederlof, J., Swennenhuis, C.M.F.: Parameterized problems complete for nondeterministic FPT time and logarithmic space. arXiv abs\/2105.14882 (2021). https:\/\/arxiv.org\/abs\/2105.14882. To appear in proceedings FOCS 2021","DOI":"10.1109\/FOCS52979.2021.00027"},{"key":"2_CR9","doi-asserted-by":"publisher","unstructured":"Bodlaender, H.L., Groenland, C., Swennenhuis, C.M.F.: Parameterized complexities of dominating and independent set reconfiguration. In: Golovach, P.A., Zehavi, M. (eds.) 16th International Symposium on Parameterized and Exact Computation, IPEC 2021. LIPIcs, vol. 214, pp. 9:1\u20139:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2021.9","DOI":"10.4230\/LIPIcs.IPEC.2021.9"},{"key":"2_CR10","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72, 1346\u20131367 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR11","doi-asserted-by":"publisher","unstructured":"Chen, Y., Flum, J., Grohe, M.: Bounded nondeterminism and alternation in parameterized complexity theory. In: 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), Aarhus, Denmark, 7\u201310 July 2003, pp. 13\u201329. IEEE Computer Society (2003). https:\/\/doi.org\/10.1109\/CCC.2003.1214407","DOI":"10.1109\/CCC.2003.1214407"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd Annual Symposium on Theory of Computing, STOC 1971, pp. 151\u2013158. ACM, New York (1971)","DOI":"10.1145\/800157.805047"},{"key":"2_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., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"2_CR14","first-page":"191","volume-title":"Complexity Theory","author":"RG Downey","year":"1993","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness III: Some structural aspects of the $$W$$ hierarchy. In: Ambos-Spies, K., Homer, S., Sch\u00f6ning, U. (eds.) Complexity Theory, pp. 191\u2013226. Cambridge University Press, Cambridge (1993)"},{"key":"2_CR15","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: Basic results. SIAM J. Comput. 24, 873\u2013921 (1995)","journal-title":"SIAM J. Comput."},{"key":"2_CR16","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: On completeness for $$W[1]$$. Theoret. Comput. Sci. 141, 109\u2013131 (1995)","journal-title":"Theoret. Comput. Sci."},{"key":"2_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999). https:\/\/doi.org\/10.1007\/978-1-4612-0515-9"},{"key":"2_CR18","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. TCS, Springer, London (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"key":"2_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/978-3-662-43948-7_34","volume-title":"Automata, Languages, and Programming","author":"MS Dregi","year":"2014","unstructured":"Dregi, M.S., Lokshtanov, D.: Parameterized complexity of bandwidth on trees. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 405\u2013416. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43948-7_34"},{"issue":"3","key":"2_CR20","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/s00453-014-9944-y","volume":"71","author":"M Elberfeld","year":"2014","unstructured":"Elberfeld, M., Stockhusen, C., Tantau, T.: On the space and circuit complexity of parameterized problems: classes and completeness. Algorithmica 71(3), 661\u2013701 (2014). https:\/\/doi.org\/10.1007\/s00453-014-9944-y","journal-title":"Algorithmica"},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0020-0190(87)90054-8","volume":"26","author":"MR Fellows","year":"1987","unstructured":"Fellows, M.R., Langston, M.A.: Nonconstructive advances in polynomial-time complexity. Inf. Process. Lett. 26, 157\u2013162 (1987)","journal-title":"Inf. Process. Lett."},{"key":"2_CR22","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1145\/44483.44491","volume":"35","author":"MR Fellows","year":"1988","unstructured":"Fellows, M.R., Langston, M.A.: Nonconstructive tools for proving polynomial-time decidability. J. ACM 35, 727\u2013739 (1988)","journal-title":"J. ACM"},{"key":"2_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/978-3-030-42071-0_2","volume-title":"Treewidth, Kernels, and Algorithms","author":"MR Fellows","year":"2020","unstructured":"Fellows, M.R., Rosamond, F.A.: Collaborating with Hans: Some remaining wonderments. In: Fomin, F.V., Kratsch, S., van Leeuwen, E.J. (eds.) Treewidth, Kernels, and Algorithms. LNCS, vol. 12160, pp. 7\u201317. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-42071-0_2"},{"issue":"4","key":"2_CR24","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1137\/S0097539703427203","volume":"33","author":"J Flum","year":"2004","unstructured":"Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM J. Comput. 33(4), 892\u2013922 (2004). https:\/\/doi.org\/10.1137\/S0097539703427203","journal-title":"SIAM J. Comput."},{"key":"2_CR25","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. TTCSAES, Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/3-540-29953-X"},{"key":"2_CR26","volume-title":"Kernelization - Theory of Parameterized Preprocessing","author":"F Fomin","year":"2019","unstructured":"Fomin, F., Loksthanov, D., Saurabh, S., Zehavi, M.: Kernelization - Theory of Parameterized Preprocessing. Cambridge University Press, Cambridge (2019)"},{"key":"2_CR27","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)"},{"key":"2_CR28","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1016\/0196-6774(84)90006-3","volume":"5","author":"EM Gurari","year":"1984","unstructured":"Gurari, E.M., Sudborough, I.H.: Improved dynamic programming algorithms for bandwidth minimization and the mincut linear arrangement problem. J. Algorithms 5, 531\u2013546 (1984)","journal-title":"J. Algorithms"},{"issue":"2","key":"2_CR29","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/j.jctb.2011.07.004","volume":"102","author":"K Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K., Kobayashi, Y., Reed, B.A.: The disjoint paths problem in quadratic time. J. Comb. Theory Ser. B 102(2), 424\u2013435 (2012). https:\/\/doi.org\/10.1016\/j.jctb.2011.07.004","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"2_CR30","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/s00453-016-0159-2","volume":"78","author":"AE Mouawad","year":"2016","unstructured":"Mouawad, A.E., Nishimura, N., Raman, V., Simjour, N., Suzuki, A.: On the parameterized complexity of reconfiguration problems. Algorithmica 78(1), 274\u2013297 (2016). https:\/\/doi.org\/10.1007\/s00453-016-0159-2","journal-title":"Algorithmica"},{"key":"2_CR31","series-title":"Oxford Lecture Series in Mathematics and Its Applications","doi-asserted-by":"publisher","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 Lecture Series in Mathematics and Its Applications, Oxford University Press, Oxford (2006)"},{"issue":"4","key":"2_CR32","doi-asserted-by":"publisher","first-page":"18:1","DOI":"10.1145\/3154856","volume":"9","author":"M Pilipczuk","year":"2018","unstructured":"Pilipczuk, M., Wrochna, M.: On space efficiency of algorithms working on structural decompositions of graphs. ACM Trans. Comput. Theory 9(4), 18:1-18:36 (2018). https:\/\/doi.org\/10.1145\/3154856","journal-title":"ACM Trans. Comput. Theory"},{"issue":"4","key":"2_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 1\u201324 (2008)","journal-title":"J. ACM"},{"key":"2_CR34","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1137\/0601042","volume":"1","author":"JB Saxe","year":"1980","unstructured":"Saxe, J.B.: Dynamic programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM J. Algebraic Discrete Methods 1, 363\u2013369 (1980)","journal-title":"SIAM J. Algebraic Discrete Methods"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-96731-4_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T00:04:26Z","timestamp":1647389066000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-96731-4_2"}},"subtitle":["Classes of Fixed Parameter Intractability"],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783030967307","9783030967314"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-96731-4_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"16 March 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Jember","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Indonesia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 March 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 March 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/walcom2022.unej.ac.id\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"89","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"34% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2-9","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The proceedings also include 3 invited papers.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}