{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:48:17Z","timestamp":1759063697341,"version":"3.37.3"},"reference-count":60,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2022,8,5]],"date-time":"2022-08-05T00:00:00Z","timestamp":1659657600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,8,5]],"date-time":"2022-08-05T00:00:00Z","timestamp":1659657600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100006730","name":"Ministerul Educa\u0163iei \u015fi Cercet\u0103rii \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"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s00453-022-01015-w","type":"journal-article","created":{"date-parts":[[2022,8,5]],"date-time":"2022-08-05T06:08:51Z","timestamp":1659679731000},"page":"3192-3222","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Optimal Centrality Computations Within Bounded Clique-Width Graphs"],"prefix":"10.1007","volume":"84","author":[{"given":"Guillaume","family":"Ducoffe","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,5]]},"reference":[{"key":"1015_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V., Wang, J.R.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 377\u2013391. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch28"},{"key":"1015_CR2","volume-title":"Graph theory. Graduate Texts in Mathematics","author":"JA Bondy","year":"2008","unstructured":"Bondy, J.A., Murty, U.S.R.: Graph theory. Graduate Texts in Mathematics, vol. 244. Springer-Verlag, London (2008)"},{"key":"1015_CR3","unstructured":"Borie, R., Johnson, J., Raghavan, V., Spinrad, J.: Robust polynomial time algorithms on clique-width $$k$$ graphs. (2002)"},{"key":"1015_CR4","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.dam.2016.04.003","volume":"211","author":"A Brandst\u00e4dt","year":"2016","unstructured":"Brandst\u00e4dt, A., Dabrowski, K.K., Huang, S., Paulusma, D.: Bounding the clique-width of $$H$$-free split graphs. Discrete Appl. Math. 211, 30\u201339 (2016)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1015_CR5","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1002\/jgt.22111","volume":"86","author":"A Brandst\u00e4dt","year":"2017","unstructured":"Brandst\u00e4dt, A., Dabrowski, K.K., Huang, S., Paulusma, D.: Bounding the Clique-Width of $$H$$-Free Chordal Graphs. J. of Graph Theory 86(1), 42\u201377 (2017)","journal-title":"J. of Graph Theory"},{"issue":"5","key":"1015_CR6","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/s00224-004-1154-6","volume":"38","author":"A Brandst\u00e4dt","year":"2005","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Le, H.-O., Mosca, R.: New graph classes of bounded clique-width. Theory of Comput. Syst. 38(5), 623\u2013645 (2005)","journal-title":"Theory of Comput. Syst."},{"issue":"4","key":"1015_CR7","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/s00224-005-1199-1","volume":"39","author":"A Brandstadt","year":"2006","unstructured":"Brandstadt, A., Engelfriet, J., Le, H.-O., Lozin, V.V.: Clique-width for $$4$$-vertex forbidden subgraphs. Theory of Comput. Syst. 39(4), 561\u2013590 (2006)","journal-title":"Theory of Comput. Syst."},{"issue":"1","key":"1015_CR8","first-page":"173","volume":"8","author":"A Brandst\u00e4dt","year":"2006","unstructured":"Brandst\u00e4dt, A., Klembt, T., Mahfud, S.: $$P_6$$-and triangle-free graphs revisited: Structure and bounded clique-width. Discrete Math. & Theor. Comput. Sci. 8(1), 173\u2013188 (2006)","journal-title":"Discrete Math. & Theor. Comput. Sci."},{"issue":"01","key":"1015_CR9","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1142\/S0129054104002364","volume":"15","author":"A Brandst\u00e4dt","year":"2004","unstructured":"Brandst\u00e4dt, A., Le, H.-O., Mosca, R.: Gem-and co-gem-free graphs have bounded clique-width. Int. J. of Foundations of Comput. Sci. 15(01), 163\u2013185 (2004)","journal-title":"Int. J. of Foundations of Comput. Sci."},{"issue":"2","key":"1015_CR10","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1016\/j.dam.2004.01.014","volume":"145","author":"A Brandst\u00e4dt","year":"2005","unstructured":"Brandst\u00e4dt, A., Le, H.-O., Mosca, R.: Chordal co-gem-free and ($$P_5$$, gem)-free graphs have bounded clique-width. Discrete Appl. Math. 145(2), 232\u2013241 (2005)","journal-title":"Discrete Appl. Math."},{"key":"1015_CR11","doi-asserted-by":"crossref","unstructured":"Bringmann, K., Husfeldt, T., Magnusson, M.: Multivariate Analysis of Orthogonal Range Searching and Graph Distances. Algorithmica, pp. 1\u201324 (2020)","DOI":"10.1007\/s00453-020-00680-z"},{"key":"1015_CR12","unstructured":"Cabello, S.: Computing the inverse geodesic length in planar graphs and graphs of bounded treewidth. Technical Report (2019). arXiv: 1908.01317"},{"issue":"9","key":"1015_CR13","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1016\/j.comgeo.2009.02.001","volume":"42","author":"S Cabello","year":"2009","unstructured":"Cabello, S., Knauer, C.: Algorithms for graphs of bounded treewidth via orthogonal range searching. Comput. Geom. 42(9), 815\u2013824 (2009)","journal-title":"Comput. Geom."},{"key":"1015_CR14","doi-asserted-by":"crossref","unstructured":"Corneil, D.G., Habib, M., Lanlignel, J.-M., Reed, B., Rotics, U.: Polynomial Time Recognition of Clique-Width $$\\le 3$$ Graphs. In: Latin American Theoretical INformatics Symposium (LATIN), volume 1776 of Lecture Notes in Computer Science, pp. 126\u2013134. Springer (2000)","DOI":"10.1007\/10719839_14"},{"issue":"4","key":"1015_CR15","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. on Comput. 34(4), 825\u2013847 (2005)","journal-title":"SIAM J. on Comput."},{"issue":"3","key":"1015_CR16","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 Trans. on Algorithms (TALG) 15(3), 1\u201357 (2019)","journal-title":"ACM Trans. on Algorithms (TALG)"},{"issue":"1","key":"1015_CR17","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. and Comput. 85(1), 12\u201375 (1990)","journal-title":"Inf. and Comput."},{"key":"1015_CR18","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. Discrete Appl. Math. 187, 70\u201381 (2015)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"1015_CR19","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theory of Comput. Syst."},{"issue":"1","key":"1015_CR20","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. Discrete Appl. Math. 131(1), 129\u2013150 (2003)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"1015_CR21","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1137\/0603021","volume":"3","author":"WH Cunningham","year":"1982","unstructured":"Cunningham, W.H.: Decomposition of directed graphs. SIAM J. on Algebr. Discrete Methods 3(2), 214\u2013228 (1982)","journal-title":"SIAM J. on Algebr. Discrete Methods"},{"key":"1015_CR22","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.dam.2015.06.030","volume":"200","author":"KK Dabrowski","year":"2016","unstructured":"Dabrowski, K.K., Paulusma, D.: Classifying the clique-width of $$H$$-free bipartite graphs. Discrete Appl. Math. 200, 43\u201351 (2016)","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"1015_CR23","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1093\/comjnl\/bxv096","volume":"59","author":"KK Dabrowski","year":"2016","unstructured":"Dabrowski, K.K., Paulusma, D.: Clique-width of graph classes defined by two forbidden induced subgraphs. The Comput. J. 59(5), 650\u2013666 (2016)","journal-title":"The Comput. J."},{"issue":"1","key":"1015_CR24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s13278-017-0479-5","volume":"8","author":"K Das","year":"2018","unstructured":"Das, K., Samanta, S., Pal, M.: Study on centrality measures in social networks: A survey. Soc. network anal. and mining 8(1), 1\u201311 (2018)","journal-title":"Soc. network anal. and mining"},{"key":"1015_CR25","volume-title":"Graph Theory. Graduate Texts in Mathematics","author":"R Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, 4th edn. Springer, Berlin (2010)","edition":"4"},{"issue":"1","key":"1015_CR26","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/s00453-008-9194-y","volume":"57","author":"FF Dragan","year":"2010","unstructured":"Dragan, F.F., Yan, C.: Collective tree spanners in graphs with bounded parameters. Algorithmica 57(1), 22\u201343 (2010)","journal-title":"Algorithmica"},{"key":"1015_CR27","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), pp. 16:1\u201316:16. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"1015_CR28","unstructured":"Ducoffe, G., Popa, A.: The b-matching problem in distance-hereditary graphs and beyond. In: International Symposium on Algorithms and Computation (ISAAC), volume 123 of Leibniz International Proceedings in Informatics, pp. 30:1\u201330:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)"},{"key":"1015_CR29","unstructured":"Ducoffe, G., Popa, A.: The use of a pruned modular decomposition for maximum matching algorithms on some graph classes. In: International Symposium on Algorithms and Computation (ISAAC), volume 123 of Leibniz International Proceedings in Informatics, pp. 6:1\u20136:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)"},{"key":"1015_CR30","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), volume\u00a01 of Lecture Notes in Computer Science, pp. 117\u2013128. Springer (2001)","DOI":"10.1007\/3-540-45477-2_12"},{"issue":"2","key":"1015_CR31","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1137\/070687256","volume":"23","author":"MR Fellows","year":"2009","unstructured":"Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width is NP-complete. SIAM J. on Discrete Math. 23(2), 909\u2013939 (2009)","journal-title":"SIAM J. on Discrete Math."},{"key":"1015_CR32","doi-asserted-by":"crossref","unstructured":"Fomin, F., Korhonen, T.: Fast fpt-approximation of branchwidth. Technical Report (2021) arXiv: 2111.03492","DOI":"10.1145\/3519935.3519996"},{"issue":"5","key":"1015_CR33","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. on Comput. 39(5), 1941\u20131956 (2010)","journal-title":"SIAM J. on Comput."},{"issue":"5","key":"1015_CR34","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. on Comput. 43(5), 1541\u20131563 (2014)","journal-title":"SIAM J. on Comput."},{"issue":"1","key":"1015_CR35","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/3280824","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 Trans. on Algorithms 15(1), 9 (2019)","journal-title":"ACM Trans. on Algorithms"},{"issue":"3","key":"1015_CR36","doi-asserted-by":"publisher","first-page":"34:1","DOI":"10.1145\/3186898","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 Trans. on Algorithms 14(3), 34:1-34:45 (2018)","journal-title":"ACM Trans. on Algorithms"},{"key":"1015_CR37","doi-asserted-by":"crossref","unstructured":"Freeman, L.C.: A set of measures of centrality based on betweenness. Sociometry, 35\u201341 (1977)","DOI":"10.2307\/3033543"},{"key":"1015_CR38","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, pp. 72\u201383. Springer (2014)","DOI":"10.1007\/978-3-642-54423-1_7"},{"key":"1015_CR39","doi-asserted-by":"crossref","unstructured":"Gajarsk\u1ef3, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: International Symposium on Parameterized and Exact Computation, pp. 163\u2013176. Springer (2013)","DOI":"10.1007\/978-3-319-03898-8_15"},{"issue":"1\u20133","key":"1015_CR40","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0012-365X(03)00232-2","volume":"273","author":"C Gavoille","year":"2003","unstructured":"Gavoille, C., Paul, C.: Distance labeling scheme and split decomposition. Discrete Math. 273(1\u20133), 115\u2013130 (2003)","journal-title":"Discrete Math."},{"issue":"1","key":"1015_CR41","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C Gavoille","year":"2004","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. J. of Algorithms 53(1), 85\u2013112 (2004)","journal-title":"J. of Algorithms"},{"key":"1015_CR42","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. Theor. comput. sci. 689, 67\u201395 (2017)","journal-title":"Theor. comput. sci."},{"issue":"2","key":"1015_CR43","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1287\/trsc.5.2.212","volume":"5","author":"A Goldman","year":"1971","unstructured":"Goldman, A.: Optimal center location in simple networks. Transp. sci. 5(2), 212\u2013221 (1971)","journal-title":"Transp. sci."},{"issue":"03","key":"1015_CR44","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. of Foundations of Comput. Sci. 11(03), 423\u2013443 (2000)","journal-title":"Int. J. of Foundations of Comput. Sci."},{"issue":"1\u20132","key":"1015_CR45","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M Habib","year":"2000","unstructured":"Habib, M., McConnell, R., Paul, C., Viennot, L.: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci. 234(1\u20132), 59\u201384 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"1015_CR46","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0378-8733(94)00248-9","volume":"17","author":"P Hage","year":"1995","unstructured":"Hage, P., Harary, F.: Eccentricity and centrality in networks. Soc. networks 17(1), 57\u201363 (1995)","journal-title":"Soc. networks"},{"issue":"3","key":"1015_CR47","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. of Comput. and Syst. Sci. 57(3), 366\u2013375 (1998)","journal-title":"J. of Comput. and Syst. Sci."},{"issue":"2","key":"1015_CR48","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J.on Comput. 13(2), 338\u2013355 (1984)","journal-title":"SIAM J.on Comput."},{"key":"1015_CR49","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), volume\u00a096 of Leibniz International Proceedings in Informatics, pp. 41:1\u201341:14. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2018)"},{"issue":"7","key":"1015_CR50","doi-asserted-by":"publisher","first-page":"2106","DOI":"10.1007\/s00453-017-0365-6","volume":"80","author":"S Kamali","year":"2018","unstructured":"Kamali, S.: Compact representation of graphs of small clique-width. Algorithmica 80(7), 2106\u20132131 (2018)","journal-title":"Algorithmica"},{"key":"1015_CR51","unstructured":"Kratsch, S., Nelles, F.: Efficient and adaptive parameterized algorithms on modular decompositions. In: European Symposia on Algorithms (ESA), pp. 55:1\u201355:15 (2018)"},{"key":"1015_CR52","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 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 38:1\u201338:15. Dagstuhl, Germany (2020). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik"},{"issue":"1\u20133","key":"1015_CR53","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/j.disc.2004.02.008","volume":"283","author":"V Lozin","year":"2004","unstructured":"Lozin, V., Rautenbach, D.: Chordal bipartite graphs of bounded tree-and clique-width. Discrete Math. 283(1\u20133), 151\u2013158 (2004)","journal-title":"Discrete Math."},{"issue":"03","key":"1015_CR54","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. of Foundations of Comput. Sci. 10(03), 329\u2013348 (1999)","journal-title":"Int. J. of Foundations of Comput. Sci."},{"issue":"4","key":"1015_CR55","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. J. of Comb. Theory, Ser. B. 96(4), 514\u2013528 (2006)","journal-title":"J. of Comb. Theory, Ser. B."},{"issue":"24","key":"1015_CR56","doi-asserted-by":"publisher","first-page":"6157","DOI":"10.1016\/j.disc.2007.11.039","volume":"308","author":"M Rao","year":"2008","unstructured":"Rao, M.: Clique-width of graphs defined by one-vertex extensions. Discrete Math. 308(24), 6157\u20136165 (2008)","journal-title":"Discrete Math."},{"issue":"4","key":"1015_CR57","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1007\/BF02289527","volume":"31","author":"G Sabidussi","year":"1966","unstructured":"Sabidussi, G.: The centrality index of a graph. Psychometrika 31(4), 581\u2013603 (1966)","journal-title":"Psychometrika"},{"issue":"14","key":"1015_CR58","doi-asserted-by":"publisher","first-page":"1885","DOI":"10.1016\/j.dam.2007.03.014","volume":"155","author":"K Suchan","year":"2007","unstructured":"Suchan, K., Todinca, I.: On powers of graphs of bounded NLC-width (clique-width). Discrete Appl. Math. 155(14), 1885\u20131893 (2007)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"1015_CR59","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1145\/316542.316548","volume":"46","author":"M Thorup","year":"1999","unstructured":"Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. J. of the ACM (JACM) 46(3), 362\u2013394 (1999)","journal-title":"J. of the ACM (JACM)"},{"issue":"1\u20133","key":"1015_CR60","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/S0012-365X(03)00295-4","volume":"276","author":"J-M Vanherpe","year":"2004","unstructured":"Vanherpe, J.-M.: Clique-width of partner-limited graphs. Discrete math. 276(1\u20133), 363\u2013374 (2004)","journal-title":"Discrete math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01015-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01015-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01015-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,26]],"date-time":"2022-10-26T07:08:43Z","timestamp":1666768123000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01015-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,5]]},"references-count":60,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["1015"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01015-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,8,5]]},"assertion":[{"value":"28 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}