{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T20:03:19Z","timestamp":1770062599758,"version":"3.49.0"},"reference-count":96,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T00:00:00Z","timestamp":1559865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006595","name":"Unitatea Executiva pentru Finantarea Invatamantului Superior, a Cercetarii, Dezvoltarii si Inovarii","doi-asserted-by":"publisher","award":["PN1819-01-01 and 17PCCDI\/2018"],"award-info":[{"award-number":["PN1819-01-01 and 17PCCDI\/2018"]}],"id":[{"id":"10.13039\/501100006595","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008952","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-15-IDEX-01"],"award-info":[{"award-number":["ANR-15-IDEX-01"]}],"id":[{"id":"10.13039\/501100008952","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,7,31]]},"abstract":"<jats:p>\n            Recently, hardness results for problems in P were achieved using reasonable complexity-theoretic assumptions such as the Strong Exponential Time Hypothesis. According to these assumptions, many graph-theoretic problems do not admit truly subquadratic algorithms. A central technique used to tackle the difficulty of the above-mentioned problems is fixed-parameter algorithms with\n            <jats:italic>polynomial dependency<\/jats:italic>\n            in the fixed parameter (P-FPT). Applying this technique to\n            <jats:italic>clique-width<\/jats:italic>\n            , an important graph parameter, remained to be done.\n          <\/jats:p>\n          <jats:p>\n            In this article, we study several graph-theoretic problems for which hardness results exist such as\n            <jats:italic>cycle problems<\/jats:italic>\n            ,\n            <jats:italic>distance problems<\/jats:italic>\n            , and\n            <jats:italic>maximum matching<\/jats:italic>\n            . We give hardness results and P-FPT algorithms, using clique-width and some of its upper bounds as parameters. We believe that our most important result is an algorithm in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>4<\/jats:sup>\n            \u22c5\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            )-time for computing a maximum matching, where\n            <jats:italic>k<\/jats:italic>\n            is either the modular-width of the graph or the\n            <jats:italic>P<\/jats:italic>\n            <jats:sub>4<\/jats:sub>\n            -sparseness. The latter generalizes many algorithms that have been introduced so far for specific subclasses such as cographs. Our algorithms are based on preprocessing methods using modular decomposition and split decomposition. Thus they can also be generalized to some graph classes with unbounded clique-width.\n          <\/jats:p>","DOI":"10.1145\/3310228","type":"journal-article","created":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T12:10:51Z","timestamp":1560168651000},"page":"1-57","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs"],"prefix":"10.1145","volume":"15","author":[{"given":"David","family":"Coudert","sequence":"first","affiliation":[{"name":"Universit\u00e9 C\u00f4te d\u2019Azur, Inria, CNRS, I3S, Sophia Antipolis Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Ducoffe","sequence":"additional","affiliation":[{"name":"National Institute for Research and Development in Informatics 8 University of Bucharest, Faculty of Mathematics and Computer Science 8 The Research Institute of the University of Bucharest ICUB, Bucure\u015fti, Romania"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandru","family":"Popa","sequence":"additional","affiliation":[{"name":"National Institute for Research and Development in Informatics 8 University of Bucharest, Faculty of Mathematics and Computer Science, Bucure\u015fti, Romania"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722241"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_2_1_3_1","volume-title":"Virginia Vassilevska Williams, and Joshua R. Wang","author":"Abboud Amir","year":"2016","unstructured":"Amir Abboud , Virginia Vassilevska Williams, and Joshua R. Wang . 2016 . Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916). SIAM , 377--391. Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. 2016. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916). SIAM, 377--391."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90073-8"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00088-0"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00140-7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)90120-7"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00062-1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90043-2"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-55751-8_9"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.43.9.842"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11917496_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.12.017"},{"key":"e_1_2_1_16_1","volume-title":"Graph Theory. Graduate Texts in Mathematics","author":"Bondy John Adrian","unstructured":"John Adrian Bondy and Uppaluri Siva Ramachandra Murty . 2008. Graph Theory. Graduate Texts in Mathematics , Vol. 244 . Springer-Verlag , London . John Adrian Bondy and Uppaluri Siva Ramachandra Murty. 2008. Graph Theory. Graduate Texts in Mathematics, Vol. 244. Springer-Verlag, London."},{"key":"e_1_2_1_17_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the European Symposia on Algorithms (ESA\u201915)","author":"Borassi Michele","unstructured":"Michele Borassi , David Coudert , Pierluigi Crescenzi , and Andrea Marino . 2015. On computing the hyperbolicity of real-world graphs . In Proceedings of the European Symposia on Algorithms (ESA\u201915) . Lecture Notes in Computer Science , Vol. 9294 . Springer , 215--226. Michele Borassi, David Coudert, Pierluigi Crescenzi, and Andrea Marino. 2015. On computing the hyperbolicity of real-world graphs. In Proceedings of the European Symposia on Algorithms (ESA\u201915). Lecture Notes in Computer Science, Vol. 9294. Springer, 215--226."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2016.03.005"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-001-8007-7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.05.022"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/10080052X"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.06.001"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2780652"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/646388.690202"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214065"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701385351"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/140954787"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.176"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.12.017"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90004-G"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.02.016"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00184-5"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0603021"},{"key":"e_1_2_1_37_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2010. Graph Theory , 4 th ed. Springer . Reinhard Diestel. 2010. Graph Theory, 4th ed. Springer.","edition":"4"},{"key":"e_1_2_1_38_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"1999","unstructured":"Rodney G. Downey and Michael R . Fellows . 1999 . Parameterized Complexity. Springer Science 8 Business Media. Rodney G. Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer Science 8 Business Media."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0024498"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00157-2"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2529989"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the International Symposium on Algorithms and Computation (ISAAC\u201918)","volume":"123","author":"Ducoffe Guillaume","year":"2018","unstructured":"Guillaume Ducoffe and Alexandru Popa . 2018 . The b-matching problem in distance-hereditary graphs and beyond . In Proceedings of the International Symposium on Algorithms and Computation (ISAAC\u201918) , Leibniz International Proceedings in Informatics , Vol. 123 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 30:1--30:13. Guillaume Ducoffe and Alexandru Popa. 2018. The b-matching problem in distance-hereditary graphs and beyond. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC\u201918), Leibniz International Proceedings in Informatics, Vol. 123. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 30:1--30:13."},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the International Symposium on Algorithms and Computation (ISAAC\u201918)","volume":"123","author":"Ducoffe Guillaume","year":"2018","unstructured":"Guillaume Ducoffe and Alexandru Popa . 2018 . The use of a pruned modular decomposition for maximum matching algorithms on some graph classes . In Proceedings of the International Symposium on Algorithms and Computation (ISAAC\u201918) , Leibniz International Proceedings in Informatics , Vol. 123 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 6:1--6:13. Guillaume Ducoffe and Alexandru Popa. 2018. The use of a pruned modular decomposition for maximum matching algorithms on some graph classes. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC\u201918), Leibniz International Proceedings in Informatics, Vol. 123. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 6:1--6:13."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45477-2_12"},{"key":"e_1_2_1_47_1","volume-title":"Tight hardness results for distance and centrality problems in constant degree graphs. CoRR abs\/1609.08403","author":"Evald Jacob","year":"2016","unstructured":"Jacob Evald and S\u00f8ren Dahlgaard . 2016. Tight hardness results for distance and centrality problems in constant degree graphs. CoRR abs\/1609.08403 ( 2016 ). arxiv:1609.08403 http:\/\/arxiv.org\/abs\/1609.08403 Jacob Evald and S\u00f8ren Dahlgaard. 2016. Tight hardness results for distance and centrality problems in constant degree graphs. CoRR abs\/1609.08403 (2016). arxiv:1609.08403 http:\/\/arxiv.org\/abs\/1609.08403"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/070687256"},{"key":"e_1_2_1_49_1","series-title":"Lecture Notes in Computer Science","volume-title":"When can graph hyperbolicity be computed in linear time? In Proceedings of the Workshop on Algorithms and Data Structures","author":"Fluschnik Till","unstructured":"Till Fluschnik , Christian Komusiewicz , George B. Mertzios , Andr\u00e9 Nichterlein , Rolf Niedermeier , and Nimrod Talmon . 2017. When can graph hyperbolicity be computed in linear time? In Proceedings of the Workshop on Algorithms and Data Structures , Lecture Notes in Computer Science , Vol. 10389 . Springer , 397--408. Till Fluschnik, Christian Komusiewicz, George B. Mertzios, Andr\u00e9 Nichterlein, Rolf Niedermeier, and Nimrod Talmon. 2017. When can graph hyperbolicity be computed in linear time? In Proceedings of the Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, Vol. 10389. Springer, 397--408."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958016.1958026"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/130910932"},{"key":"e_1_2_1_52_1","first-page":"9","article-title":"Clique-width III: Hamiltonian cycle and the odd case of graph coloring","volume":"15","author":"Fomin Fedor V.","year":"2019","unstructured":"Fedor V. Fomin , Petr A. Golovach , Daniel Lokshtanov , Saket Saurabh , and Meirav Zehavi . 2019 . Clique-width III: Hamiltonian cycle and the odd case of graph coloring . ACM Trans. Algor. 15 , 1 (2019), 9 . Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. 2019. Clique-width III: Hamiltonian cycle and the odd case of graph coloring. ACM Trans. Algor. 15, 1 (2019), 9.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186898"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054199000368"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00081-1"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2015.02.002"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808776"},{"key":"e_1_2_1_59_1","volume-title":"Proceedings of the ACM Symposium on the Theory of Computing (STOC\u201983)","author":"Harold","unstructured":"Harold N. Gabow and Robert Endre Tarjan. 1983. A linear-time algorithm for a special case of disjoint set union . In Proceedings of the ACM Symposium on the Theory of Computing (STOC\u201983) . ACM, 246--251. Harold N. Gabow and Robert Endre Tarjan. 1983. A linear-time algorithm for a special case of disjoint set union. In Proceedings of the ACM Symposium on the Theory of Computing (STOC\u201983). ACM, 246--251."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03898-8_15"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020961"},{"key":"e_1_2_1_63_1","volume-title":"Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA\u201910)","volume":"6460","author":"Ganian Robert","year":"2010","unstructured":"Robert Ganian . 2010 . Thread graphs, linear rank-width and their algorithmic applications . In Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA\u201910) , Lecture Notes in Computer Science , Vol. 6460 . Springer, 38--42. Robert Ganian. 2010. Thread graphs, linear rank-width and their algorithmic applications. In Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA\u201910), Lecture Notes in Computer Science, Vol. 6460. Springer, 38--42."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00232-2"},{"key":"e_1_2_1_65_1","first-page":"17","article-title":"On P<sub>4<\/sub>-tidy graphs","volume":"1","author":"Giakoumakis Vassilis","year":"1997","unstructured":"Vassilis Giakoumakis , Florian Roussel , and Henri Thuillier . 1997 . On P<sub>4<\/sub>-tidy graphs . Discr. Math. Theor. Comput. Sci. 1 , 1 (1997), 17 -- 41 . http:\/\/dmtcs.episciences.org\/232 Vassilis Giakoumakis, Florian Roussel, and Henri Thuillier. 1997. On P<sub>4<\/sub>-tidy graphs. Discr. Math. Theor. Comput. Sci. 1, 1 (1997), 17--41. http:\/\/dmtcs.episciences.org\/232","journal-title":"Discr. Math. Theor. Comput. Sci."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.05.017"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.05.007"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054100000260"},{"key":"e_1_2_1_69_1","volume-title":"Essays in Group Theory","author":"Gromov Mikha\u00efl","unstructured":"Mikha\u00efl Gromov . 1987. Hyperbolic groups . In Essays in Group Theory . Springer , 75--263. Mikha\u00efl Gromov. 1987. Hyperbolic groups. In Essays in Group Theory. Springer, 75--263."},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-40064-8_19"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2010.01.001"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(79)90069-8"},{"key":"e_1_2_1_73_1","volume-title":"Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC\u201916)","volume":"63","author":"Husfeldt Thore","year":"2016","unstructured":"Thore Husfeldt . 2016 . Computing graph distances parameterized by treewidth and diameter . In Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC\u201916) , Leibniz International Proceedings in Informatics , Vol. 63 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 16:1--16:11. Thore Husfeldt. 2016. Computing graph distances parameterized by treewidth and diameter. In Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC\u201916), Leibniz International Proceedings in Informatics, Vol. 63. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 16:1--16:11."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796440"},{"key":"e_1_2_1_75_1","volume-title":"Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS\u201918)","volume":"96","author":"Iwata Yoichi","year":"2018","unstructured":"Yoichi Iwata , Tomoaki Ogasawara , and Naoto Ohsaka . 2018 . On the power of tree-depth for fully polynomial FPT algorithms . In Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS\u201918) , Leibniz International Proceedings in Informatics , Vol. 96 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 41:1--41:14. Yoichi Iwata, Tomoaki Ogasawara, and Naoto Ohsaka. 2018. On the power of tree-depth for fully polynomial FPT algorithms. In Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS\u201918), Leibniz International Proceedings in Informatics, Vol. 96. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 41:1--41:14."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480191196812"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1515\/crll.1869.70.185"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1981.21"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441435"},{"key":"e_1_2_1_80_1","volume-title":"Proceedings of the European Symposia on Algorithms (ESA\u201918)","author":"Kratsch Stefan","year":"2018","unstructured":"Stefan Kratsch and Florian Nelles . 2018 . Efficient and adaptive parameterized algorithms on modular decompositions . In Proceedings of the European Symposia on Algorithms (ESA\u201918) . 55:1--55:15. Stefan Kratsch and Florian Nelles. 2018. Efficient and adaptive parameterized algorithms on modular decompositions. In Proceedings of the European Symposia on Algorithms (ESA\u201918). 55:1--55:15."},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118216.3118283"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054199000241"},{"key":"e_1_2_1_84_1","volume-title":"Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS\u201917)","volume":"83","author":"Mertzios George B.","year":"2017","unstructured":"George B. Mertzios , Andr\u00e9 Nichterlein , and Rolf Niedermeier . 2017 . The power of linear-time data reduction for maximum matching . In Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS\u201917) , Leibniz International Proceedings in Informatics , Vol. 83 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 46:1--46:14. George B. Mertzios, Andr\u00e9 Nichterlein, and Rolf Niedermeier. 2017. The power of linear-time data reduction for maximum matching. In Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS\u201917), Leibniz International Proceedings in Informatics, Vol. 83. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 46:1--46:14."},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1980.12"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90208-2"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.10.006"},{"key":"e_1_2_1_89_1","first-page":"1","article-title":"Topology manipulations for speeding betweenness centrality computation","volume":"3","author":"Puzis Rami","year":"2015","unstructured":"Rami Puzis , Yuval Elovici , Polina Zilberman , Shlomi Dolev , and Ulrik Brandes . 2015 . Topology manipulations for speeding betweenness centrality computation . J. Complex Netw. 3 , 1 (Mar. 2015), 84--112. Rami Puzis, Yuval Elovici, Polina Zilberman, Shlomi Dolev, and Ulrik Brandes. 2015. Topology manipulations for speeding betweenness centrality computation. J. Complex Netw. 3, 1 (Mar. 2015), 84--112.","journal-title":"J. Complex Netw."},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03898-8_26"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.11.039"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.11.013"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488673"},{"key":"e_1_2_1_95_1","volume-title":"Topics in Combinatorics and Graph Theory","author":"Scheffler Petra","unstructured":"Petra Scheffler . 1990. A linear algorithm for the pathwidth of trees . In Topics in Combinatorics and Graph Theory . Springer , 613--620. Petra Scheffler. 1990. A linear algorithm for the pathwidth of trees. In Topics in Combinatorics and Graph Theory. Springer, 613--620."},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90100-3"},{"key":"e_1_2_1_98_1","series-title":"Lecture Notes in Computer Science","volume-title":"Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP\u201908)","author":"Tedder Marc","unstructured":"Marc Tedder , Derek G. Corneil , Michel Habib , and Christophe Paul . 2008. Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP\u201908) , Lecture Notes in Computer Science , Vol. 5125 . Springer , 634--645. Marc Tedder, Derek G. Corneil, Michel Habib, and Christophe Paul. 2008. Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP\u201908), Lecture Notes in Computer Science, Vol. 5125. Springer, 634--645."},{"key":"e_1_2_1_99_1","volume-title":"Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC\u201915)","volume":"43","author":"Williams Virginia Vassilevska","year":"2015","unstructured":"Virginia Vassilevska Williams . 2015 . Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (Invited talk) . In Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC\u201915) , Leibniz International Proceedings in Informatics , Vol. 43 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 16--28. Virginia Vassilevska Williams. 2015. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (Invited talk). In Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC\u201915), Leibniz International Proceedings in Informatics, Vol. 43. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 16--28."},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.67"},{"key":"e_1_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90230-7"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3310228","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3310228","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:13:16Z","timestamp":1750212796000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3310228"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,7]]},"references-count":96,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7,31]]}},"alternative-id":["10.1145\/3310228"],"URL":"https:\/\/doi.org\/10.1145\/3310228","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,7]]},"assertion":[{"value":"2018-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}