{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:57Z","timestamp":1740109317333,"version":"3.37.3"},"reference-count":81,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2022,7,2]],"date-time":"2022-07-02T00:00:00Z","timestamp":1656720000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,7,2]],"date-time":"2022-07-02T00:00:00Z","timestamp":1656720000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100006730","name":"Ministerul Educa\u0163iei \u015fi Cercet\u0103 rii \u015etiin\u0163ifice","doi-asserted-by":"publisher","award":["PN-19-37-04-01"],"award-info":[{"award-number":["PN-19-37-04-01"]}],"id":[{"id":"10.13039\/501100006730","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007336","name":"Universitatea din Bucure\u015fti","doi-asserted-by":"publisher","award":["15109-26.07.2021"],"award-info":[{"award-number":["15109-26.07.2021"]}],"id":[{"id":"10.13039\/501100007336","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s00453-022-00999-9","type":"journal-article","created":{"date-parts":[[2022,7,2]],"date-time":"2022-07-02T06:03:03Z","timestamp":1656741783000},"page":"3489-3520","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Maximum Matching in Almost Linear Time on Graphs of Bounded Clique-Width"],"prefix":"10.1007","volume":"84","author":[{"given":"Guillaume","family":"Ducoffe","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,2]]},"reference":[{"key":"999_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Vassilevska\u00a0Williams, V., Wang, J.R.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In: Proceedings of the twenty-seventh annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pages 377\u2013391. SIAM, (2016)","DOI":"10.1137\/1.9781611974331.ch28"},{"key":"999_CR2","doi-asserted-by":"crossref","unstructured":"Alman, J., Vassilevska\u00a0Williams, V.: A refined laser method and faster matrix multiplication. In :Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522\u2013539. SIAM, (2021)","DOI":"10.1137\/1.9781611976465.32"},{"key":"999_CR3","unstructured":"Anari, N., Vazirani, V.: Matching Is as Easy as the Decision Problem, in the NC Model. In: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 54:1\u201354:25. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, (2020)"},{"issue":"3","key":"999_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0020-0190(87)90178-5","volume":"24","author":"R Anstee","year":"1987","unstructured":"Anstee, R.: A polynomial algorithm for b-matchings: an alternative approach. Inf. Process. Lett. 24(3), 153\u2013157 (1987)","journal-title":"Inf. Process. Lett."},{"key":"999_CR5","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.jcss.2019.02.004","volume":"103","author":"M Bentert","year":"2019","unstructured":"Bentert, M., Fluschnik, T., Nichterlein, A., Niedermeier, R.: Parameterized aspects of triangle enumeration. J. Comput. Syst. Sci. 103, 61\u201377 (2019)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"999_CR6","first-page":"258","volume":"247","author":"C Berge","year":"1958","unstructured":"Berge, C.: Sur le couplage maximum dun graphe. COMPTES RENDUS HEBDOMADAIRES DES SEANCES DE L\u2019ACADEMIE DES SCIENCES 247(3), 258\u2013259 (1958)","journal-title":"COMPTES RENDUS HEBDOMADAIRES DES SEANCES DE L\u2019ACADEMIE DES SCIENCES"},{"key":"999_CR7","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph theory. Graduate Texts in Mathematics, vol. 244. Springer-Verlag, London (2008)","DOI":"10.1007\/978-1-84628-970-5"},{"key":"999_CR8","doi-asserted-by":"crossref","unstructured":"Carmosino, M., Gao, J., Impagliazzo, R., Mihajlin, I., Paturi, R., Schneider, S.: Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 261\u2013270, (2016)","DOI":"10.1145\/2840728.2840746"},{"key":"999_CR9","doi-asserted-by":"crossref","unstructured":"Chang, M.: Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs. In ISAAC, pages 146\u2013155. Springer, (1996)","DOI":"10.1007\/BFb0009490"},{"issue":"6","key":"999_CR10","doi-asserted-by":"publisher","first-page":"1635","DOI":"10.1137\/S0097539793256223","volume":"26","author":"J Cheriyan","year":"1997","unstructured":"Cheriyan, J.: Randomized $$\\tilde{\\cal{O}}(M(|V|))$$ Algorithms for Problems in Matching Theory. SIAM J. Comput. 26(6), 1635\u20131655 (1997)","journal-title":"SIAM J. Comput."},{"key":"999_CR11","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.dam.2015.07.008","volume":"200","author":"V Cohen-Addad","year":"2016","unstructured":"Cohen-Addad, V., Habib, M., de Montgolfier, F.: Algorithmic aspects of switch cographs. Discret. Appl. Math. 200, 23\u201342 (2016)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"999_CR12","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1137\/S0097539701385351","volume":"34","author":"DG Corneil","year":"2005","unstructured":"Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput. 34(4), 825\u2013847 (2005)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"999_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3310228","volume":"15","author":"D Coudert","year":"2019","unstructured":"Coudert, D., Ducoffe, G., Popa, A.: Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. ACM Transactions on Algorithms (TALG) 15(3), 1\u201357 (2019)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"issue":"1","key":"999_CR14","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. Comput."},{"key":"999_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977619","volume-title":"Graph structure and monadic second-order logic: a language-theoretic approach","author":"B Courcelle","year":"2012","unstructured":"Courcelle, B., Engelfriet, J.: Graph structure and monadic second-order logic: a language-theoretic approach, vol. 138. Cambridge University Press, Cambridge (2012)"},{"key":"999_CR16","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.dam.2015.02.016","volume":"187","author":"B Courcelle","year":"2015","unstructured":"Courcelle, B., Heggernes, P., Meister, D., Papadopoulos, C., Rotics, U.: A characterisation of clique-width through nested partitions. Discret. Appl. Math. 187, 70\u201381 (2015)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"999_CR17","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems 33(2), 125\u2013150 (2000)","journal-title":"Theory of Computing Systems"},{"issue":"1\u20132","key":"999_CR18","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(93)90064-Z","volume":"109","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theoret. Comput. Sci. 109(1\u20132), 49\u201382 (1993)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"999_CR19","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discret. Appl. Math. 101(1), 77\u2013114 (2000)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"999_CR20","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/s00224-009-9211-9","volume":"47","author":"B Courcelle","year":"2010","unstructured":"Courcelle, B., Twigg, A.: Constrained-path labellings on graphs of bounded clique-width. Theory of Computing Systems 47(2), 531\u2013567 (2010)","journal-title":"Theory of Computing Systems"},{"issue":"1","key":"999_CR21","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0166-218X(02)00421-3","volume":"131","author":"B Courcelle","year":"2003","unstructured":"Courcelle, B., Vanicat, R.: Query efficient implementation of graphs of bounded clique-width. Discret. Appl. Math. 131(1), 129\u2013150 (2003)","journal-title":"Discret. Appl. Math."},{"key":"999_CR22","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.dam.2015.06.030","volume":"200","author":"K Dabrowski","year":"2016","unstructured":"Dabrowski, K., Paulusma, D.: Classifying the clique-width of $$H$$-free bipartite graphs. Discret. Appl. Math. 200, 43\u201351 (2016)","journal-title":"Discret. Appl. Math."},{"issue":"1\u20133","key":"999_CR23","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0166-218X(98)00006-7","volume":"84","author":"E Dahlhaus","year":"1998","unstructured":"Dahlhaus, E., Karpinski, M.: Matching and multidimensional matching in chordal and strongly chordal graphs. Discret. Appl. Math. 84(1\u20133), 79\u201391 (1998)","journal-title":"Discret. Appl. Math."},{"key":"999_CR24","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics. 4th edn. Springer, (2010)","DOI":"10.1007\/978-3-642-14279-6"},{"issue":"5","key":"999_CR25","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/S0022-0000(70)80041-1","volume":"4","author":"J Doner","year":"1970","unstructured":"Doner, J.: Tree acceptors and some of their applications. J. Comput. Syst. Sci. 4(5), 406\u2013451 (1970)","journal-title":"J. Comput. Syst. Sci."},{"key":"999_CR26","doi-asserted-by":"crossref","unstructured":"Dong, S., Lee, Y.T., Ye G.: A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1784\u20131797, (2021)","DOI":"10.1145\/3406325.3451056"},{"key":"999_CR27","doi-asserted-by":"crossref","unstructured":"Dragan, F.: On greedy matching ordering and greedy matchable graphs. In: WG\u201997, volume 1335 of LNCS, pages 184\u2013198. Springer, (1997)","DOI":"10.1007\/BFb0024498"},{"key":"999_CR28","unstructured":"Ducoffe, G.: Maximum Matching in Almost Linear Time on Graphs of Bounded Clique-Width. In: Golovach, P.A., Zehavi, M.: (eds), International Symposium on Parameterized and Exact Computation (IPEC 2021), volume 214 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1\u201315:17. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, (2021)"},{"key":"999_CR29","unstructured":"Ducoffe, G.: Optimal Centrality Computations Within Bounded Clique-Width Graphs. In: Golovach, P.A., Zehavi, M.: (eds) International Symposium on Parameterized and Exact Computation (IPEC 2021), volume 214 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1\u201316:16. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, (2021)"},{"key":"999_CR30","unstructured":"Ducoffe, G., Popa, A.: The b-Matching Problem in Distance-Hereditary Graphs and Beyond. In: 29th International Symposium on Algorithms and Computation (ISAAC 2018), volume 123 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1\u201330:13. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, (2018)"},{"key":"999_CR31","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/j.dam.2020.12.018","volume":"291","author":"G Ducoffe","year":"2021","unstructured":"Ducoffe, G., Popa, A.: The use of a pruned modular decomposition for Maximum Matching algorithms on some graph classes. Discret. Appl. Math. 291, 201\u2013222 (2021)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"999_CR32","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Canadian J. of mathematics 17(3), 449\u2013467 (1965)","journal-title":"Canadian J. of mathematics"},{"key":"999_CR33","doi-asserted-by":"crossref","unstructured":"Espelage, W., Gurski, F., Wanke, E.: How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time. In: International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2001), volume\u00a01 of Lecture Notes in Computer Science, pages 117\u2013128. Springer, (2001)","DOI":"10.1007\/3-540-45477-2_12"},{"key":"999_CR34","doi-asserted-by":"crossref","unstructured":"T.\u00a0Fluschnik, G.\u00a0Mertzios, and A.\u00a0Nichterlein. Kernelization lower bounds for finding constant-size subgraphs. In Conference on Computability in Europe, pages 183\u2013193. Springer, 2018","DOI":"10.1007\/978-3-319-94418-0_19"},{"key":"999_CR35","doi-asserted-by":"crossref","unstructured":"Fomin, F., Korhonen, T.: Fast FPT-Approximation of Branchwidth. Technical Report 2111.03492, arXiv, (2021)","DOI":"10.1145\/3519935.3519996"},{"issue":"5","key":"999_CR36","doi-asserted-by":"publisher","first-page":"1941","DOI":"10.1137\/080742270","volume":"39","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Intractability of clique-width parameterizations. SIAM J. Comput. 39(5), 1941\u20131956 (2010)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"999_CR37","doi-asserted-by":"publisher","first-page":"1541","DOI":"10.1137\/130910932","volume":"43","author":"FV Fomin","year":"2014","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Almost optimal lower bounds for problems parameterized by clique-width. SIAM J. Comput. 43(5), 1541\u20131563 (2014)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"999_CR38","first-page":"9","volume":"15","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S., Zehavi, M.: Clique-width III: Hamiltonian Cycle and the Odd Case of Graph Coloring. ACM Transactions on Algorithms (TALG) 15(1), 9 (2019)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"issue":"3","key":"999_CR39","first-page":"34:1","volume":"14","author":"FV Fomin","year":"2018","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Pilipczuk, M., Wrochna, M.: Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. ACM Transactions on Algorithms (TALG) 14(3), 34:1-34:45 (2018)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"issue":"04","key":"999_CR40","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1142\/S0129054199000368","volume":"10","author":"J-L Fouquet","year":"1999","unstructured":"Fouquet, J.-L., Giakoumakis, V., Vanherpe, J.-M.: Bipartite graphs totally decomposable by canonical decomposition. International J. of Foundations of Computer Science 10(04), 513\u2013533 (1999)","journal-title":"International J. of Foundations of Computer Science"},{"issue":"6","key":"999_CR41","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/S0020-0190(97)00081-1","volume":"62","author":"J-L Fouquet","year":"1997","unstructured":"Fouquet, J.-L., Parfenoff, I., Thuillier, H.: An $${O}(n)$$-time algorithm for maximum matching in $${P}_4$$-tidy graphs. Inf. Process. Lett. 62(6), 281\u2013287 (1997)","journal-title":"Inf. Process. Lett."},{"key":"999_CR42","doi-asserted-by":"crossref","unstructured":"F\u00fcrer, M.: A natural generalization of bounded tree-width and bounded clique-width. In: Latin American Symposium on Theoretical Informatics, pages 72\u201383. Springer, (2014)","DOI":"10.1007\/978-3-642-54423-1_7"},{"issue":"3","key":"999_CR43","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3183369","volume":"14","author":"H Gabow","year":"2018","unstructured":"Gabow, H.: Data structures for weighted matching and extensions to b-matching and f-factors. ACM Transactions on Algorithms (TALG) 14(3), 1\u201380 (2018)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"issue":"2","key":"999_CR44","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1137\/16M1106195","volume":"50","author":"H Gabow","year":"2021","unstructured":"Gabow, H., Sankowski, P.: Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors. SIAM J. Comput. 50(2), 440\u2013486 (2021)","journal-title":"SIAM J. Comput."},{"key":"999_CR45","first-page":"373","volume":"8","author":"T Gallai","year":"1963","unstructured":"Gallai, T.: Kritische graphen II. Magyar Tud. Akad. Mat. Kutato Int. Kozl. 8, 373\u2013395 (1963)","journal-title":"Magyar Tud. Akad. Mat. Kutato Int. Kozl."},{"key":"999_CR46","first-page":"401","volume":"9","author":"T Gallai","year":"1964","unstructured":"Gallai, T.: Maximale systeme unabhangiger kanten. Magyar Tud. Akad. Mat. Kutato Int. Kozl. 9, 401\u2013413 (1964)","journal-title":"Magyar Tud. Akad. Mat. Kutato Int. Kozl."},{"key":"999_CR47","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0927-0507(05)80120-3","volume":"7","author":"A Gerards","year":"1995","unstructured":"Gerards, A.: Matching. Handbooks Oper. Res. Management Sci. 7, 135\u2013224 (1995)","journal-title":"Handbooks Oper. Res. Management Sci."},{"key":"999_CR48","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.tcs.2017.05.017","volume":"689","author":"AC Giannopoulou","year":"2017","unstructured":"Giannopoulou, A.C., Mertzios, G.B., Niedermeier, R.: Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. Theoretical Comput. Sci. 689, 67\u201395 (2017)","journal-title":"Theoretical Comput. Sci."},{"issue":"3","key":"999_CR49","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/nav.3800140304","volume":"14","author":"F Glover","year":"1967","unstructured":"Glover, F.: Maximum matching in a convex bipartite graph. Naval Research Logistics (NRL) 14(3), 313\u2013316 (1967)","journal-title":"Naval Research Logistics (NRL)"},{"issue":"03","key":"999_CR50","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1142\/S0129054100000260","volume":"11","author":"MC Golumbic","year":"2000","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of some perfect graph classes. Int. J. Found. Comput. Sci. 11(03), 423\u2013443 (2000)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"3","key":"999_CR51","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1006\/jcss.1998.1592","volume":"57","author":"T Hagerup","year":"1998","unstructured":"Hagerup, T., Katajainen, J., Nishimura, N., Ragde, P.: Characterizing multiterminal flow networks and computing flows in networks of small treewidth. J. Comput. Syst. Sci. 57(3), 366\u2013375 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"999_CR52","unstructured":"Hegerfeld, F., Kratsch, S.: On Adaptive Algorithms for Maximum Matching. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132, pages 71:1\u201371:16. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, (2019)"},{"key":"999_CR53","unstructured":"Iwata, Y., Ogasawara, T., Ohsaka, N.: On the power of tree-depth for fully polynomial FPT algorithms. In: International Symposium on Theoretical Aspects of Computer Science (STACS 2018), volume\u00a096 of Leibniz International Proceedings in Informatics (LIPIcs), pages 41:1\u201341:14. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, (2018)"},{"issue":"185","key":"999_CR54","first-page":"81","volume":"70","author":"C Jordan","year":"1869","unstructured":"Jordan, C.: Sur les assemblages de lignes. J. Reine Angew. Math. 70(185), 81 (1869)","journal-title":"J. Reine Angew. Math."},{"key":"999_CR55","unstructured":"Kratsch, S., Nelles, F.: Efficient and Adaptive Parameterized Algorithms on Modular Decompositions. In: Annual European Symposium on Algorithms (ESA 2018), pp 55:1\u201355:15, (2018)"},{"key":"999_CR56","unstructured":"Kratsch, S., Nelles, F.: Efficient Parameterized Algorithms for Computing All-Pairs Shortest Paths. In: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), volume 154, pp. 38:1\u201338:15. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, (2020)"},{"key":"999_CR57","unstructured":"Lee, Y.T., Sidford, A.: Path Finding I: Solving Linear Programs with $$\\tilde{\\cal{O}}(\\sqrt{\\text{rank}})$$ Linear System Solves. Technical Report 1312.6677, arXiv, (2013)"},{"issue":"4","key":"999_CR58","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0020-0190(93)90117-R","volume":"45","author":"Y Liang","year":"1993","unstructured":"Liang, Y., Rhee, C.: Finding a maximum matching in a circular-arc graph. Inf. Process. Lett. 45(4), 185\u2013190 (1993)","journal-title":"Inf. Process. Lett."},{"key":"999_CR59","volume-title":"Matching theory","author":"L Lov\u00e1sz","year":"2009","unstructured":"Lov\u00e1sz, L., Plummer, M.: Matching theory, vol. 367. American Mathematical Soc, Providence, RI (2009)"},{"key":"999_CR60","doi-asserted-by":"crossref","unstructured":"Madry, A.: Navigating central path with electrical flows: From flows to matchings, and back. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 253\u2013262. IEEE, (2013)","DOI":"10.1109\/FOCS.2013.35"},{"issue":"03","key":"999_CR61","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1142\/S0129054199000241","volume":"10","author":"JA Makowsky","year":"1999","unstructured":"Makowsky, J.A., Rotics, U.: On the clique-width of graphs with few $$P_4$$\u2019s. Int. J. Found. Comput. Sci. 10(03), 329\u2013348 (1999)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"999_CR62","doi-asserted-by":"publisher","first-page":"2820","DOI":"10.1137\/17M1120920","volume":"32","author":"G Mertzios","year":"2018","unstructured":"Mertzios, G., Nichterlein, A., Niedermeier, R.: A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs. SIAM J. Discret. Math. 32(4), 2820\u20132835 (2018)","journal-title":"SIAM J. Discret. Math."},{"key":"999_CR63","unstructured":"Mertzios, G.B., Nichterlein, A., Niedermeier, R.: The power of linear-time data reduction for maximum matching. In: International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), volume\u00a083 of Leibniz International Proceedings in Informatics (LIPIcs), pages 46:1\u201346:14. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, (2017)"},{"key":"999_CR64","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V.: An $${O}(\\sqrt{V} {E})$$ algorithm for finding maximum matching in general graphs. In: FOCS\u201980, pp. 17\u201327. IEEE, (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"999_CR65","unstructured":"Moitra, A., Johnson, R.: A parallel algorithm for maximum matching on interval graphs. In: ICPP, (1989)"},{"issue":"1","key":"999_CR66","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jctb.2005.03.003","volume":"95","author":"S Oum","year":"2005","unstructured":"Oum, S.: Rank-width and vertex-minors. Journal of Combinatorial Theory, Series B 95(1), 79\u2013100 (2005)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"4","key":"999_CR67","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S Oum","year":"2006","unstructured":"Oum, S., Seymour, P.: Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B 96(4), 514\u2013528 (2006)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"999_CR68","unstructured":"Padberg, M., Rao, M.: The Russian method for linear inequalities III: Bounded integer programming. Technical Report\u00a078, INRIA, (1981)"},{"key":"999_CR69","unstructured":"Pulleyblank, W.: Faces of Matching Polyhedra. PhD thesis, Univ. of Waterloo, Dept. Combinatorics and Optimization, (1973)"},{"issue":"14","key":"999_CR70","doi-asserted-by":"publisher","first-page":"2768","DOI":"10.1016\/j.dam.2007.11.013","volume":"156","author":"M Rao","year":"2008","unstructured":"Rao, M.: Solving some NP-complete problems using split decomposition. Discret. Appl. Math. 156(14), 2768\u20132780 (2008)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"999_CR71","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF01580724","volume":"40","author":"J Renegar","year":"1988","unstructured":"Renegar, J.: A polynomial-time algorithm, based on Newton\u2019s method, for linear programming. Math. Program. 40(1), 59\u201393 (1988)","journal-title":"Math. Program."},{"issue":"1","key":"999_CR72","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J Thatcher","year":"1968","unstructured":"Thatcher, J., Wright, J.: Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical systems theory 2(1), 57\u201381 (1968)","journal-title":"Mathematical systems theory"},{"issue":"S20","key":"999_CR73","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1002\/qua.560300762","volume":"30","author":"N Trinajsti\u0107","year":"1986","unstructured":"Trinajsti\u0107, N., Klein, D., Randi\u0107, M.: On some solved and unsolved problems of chemical graph theory. Int. J. Quantum Chem. 30(S20), 699\u2013742 (1986)","journal-title":"Int. J. Quantum Chem."},{"issue":"2","key":"999_CR74","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1112\/jlms\/s1-22.2.107","volume":"1","author":"W Tutte","year":"1947","unstructured":"Tutte, W.: The factorization of linear graphs. J. Lond. Math. Soc. 1(2), 107\u2013111 (1947)","journal-title":"J. Lond. Math. Soc."},{"issue":"1954","key":"999_CR75","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"W Tutte","year":"1954","unstructured":"Tutte, W.: A short proof of the factor theorem for finite graphs. Canad. J. Math 6(1954), 347\u2013352 (1954)","journal-title":"Canad. J. Math"},{"key":"999_CR76","doi-asserted-by":"publisher","first-page":"1101","DOI":"10.4153\/CJM-1967-101-8","volume":"19","author":"W Tutte","year":"1967","unstructured":"Tutte, W.: Antisymmetrical digraphs. Can. J. Math. 19, 1101\u20131117 (1967)","journal-title":"Can. J. Math."},{"key":"999_CR77","unstructured":"Vassilevska\u00a0Williams, V.: On some fine-grained questions in algorithms and complexity. In: Proceedings of the ICM, volume\u00a03, pages 3431\u20133472. World Scientific, (2018)"},{"issue":"5","key":"999_CR78","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3186893","volume":"65","author":"V Vassilevska Williams","year":"2018","unstructured":"Vassilevska Williams, V., Williams, R.: Subcubic equivalences between path, matrix, and triangle problems. Journal of the ACM (JACM) 65(5), 1\u201338 (2018)","journal-title":"Journal of the ACM (JACM)"},{"issue":"2","key":"999_CR79","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0020-0190(93)90230-7","volume":"47","author":"M-S Yu","year":"1993","unstructured":"Yu, M.-S., Yang, C.-H.: An $${O}(n)$$-time algorithm for maximum matching on cographs. Inf. Process. Lett. 47(2), 89\u201393 (1993)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"999_CR80","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s00453-012-9625-7","volume":"66","author":"R Yuster","year":"2013","unstructured":"Yuster, R.: Maximum matching in regular and almost regular graphs. Algorithmica 66(1), 87\u201392 (2013)","journal-title":"Algorithmica"},{"key":"999_CR81","unstructured":"Yuster, R., Zwick, U.: Maximum matching in graphs with an excluded minor. In: Proceedings of the eighteenth annual ACM-SIAM Symposium on Discrete Algorithms, pages 108\u2013117. Society for Industrial and Applied Mathematics, (2007)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00999-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00999-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00999-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,26]],"date-time":"2022-10-26T07:09:09Z","timestamp":1666768149000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00999-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,2]]},"references-count":81,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["999"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00999-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,7,2]]},"assertion":[{"value":"28 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"This work was supported by Grant TC ICUB-SSE 15109-26.07.2021, \u201cThe complexity landscape of Maximum Matching\u201d. It was also supported by project PN-19-37-04-01 \u201cNew solutions for complex problems in current ICT research fields based on modelling and optimization\u201d, funded by the Romanian Core Program of the Ministry of Research and Innovation (MCI) 2019-2022.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}]}}