{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:25:40Z","timestamp":1758273940557,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2018,10,13]],"date-time":"2018-10-13T00:00:00Z","timestamp":1539388800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["DAMM (NI 369\/13-2)","MAGZ (KO 3669\/4-1)"],"award-info":[{"award-number":["DAMM (NI 369\/13-2)","MAGZ (KO 3669\/4-1)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/P020372\/1"],"award-info":[{"award-number":["EP\/P020372\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001655","name":"Deutscher Akademischer Austauschdienst","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005386","name":"Israeli Centers for Research Excellence","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005386","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,5]]},"DOI":"10.1007\/s00453-018-0522-6","type":"journal-article","created":{"date-parts":[[2018,10,13]],"date-time":"2018-10-13T05:26:32Z","timestamp":1539408392000},"page":"2016-2045","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["When Can Graph Hyperbolicity be Computed in Linear Time?"],"prefix":"10.1007","volume":"81","author":[{"given":"Till","family":"Fluschnik","sequence":"first","affiliation":[]},{"given":"Christian","family":"Komusiewicz","sequence":"additional","affiliation":[]},{"given":"George B.","family":"Mertzios","sequence":"additional","affiliation":[]},{"given":"Andr\u00e9","family":"Nichterlein","sequence":"additional","affiliation":[]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[]},{"given":"Nimrod","family":"Talmon","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,10,13]]},"reference":[{"key":"522_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Vassilevska Williams, V., Wang, J. R.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In: Proceedings of 27th SODA, pp. 377\u2013391. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch28"},{"issue":"1","key":"522_CR2","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1002\/net.21631","volume":"67","author":"M Abu-Ata","year":"2016","unstructured":"Abu-Ata, M., Dragan, F.F.: Metric tree-like structures in real-world networks: an empirical study. Networks 67(1), 49\u201368 (2016)","journal-title":"Networks"},{"key":"522_CR3","unstructured":"Bentert, M., Dittmann, A., Kellerhals, L., Nichterlein, A., Niedermeier, R.: Towards improving Brandes\u2019 algorithm for betweenness centrality. arXiv:1802.06701 (2018). Extended abstract to appear in Proceedings of 29th ISAAC"},{"key":"522_CR4","doi-asserted-by":"crossref","unstructured":"Borassi, M., Coudert, D., Crescenzi, P., Marino, A.: On computing the hyperbolicity of real-world graphs. In: Proceedings of 23rd ESA, vol. 9294 of LNCS, pp. 215\u2013226. Springer, Berlin (2015)","DOI":"10.1007\/978-3-662-48350-3_19"},{"key":"522_CR5","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.entcs.2016.03.005","volume":"322","author":"M Borassi","year":"2016","unstructured":"Borassi, M., Crescenzi, P., Habib, M.: Into the square: on the complexity of some quadratic-time solvable problems. Electron. Notes Theor. Comput. Sci. 322, 51\u201367 (2016)","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"522_CR6","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: a Survey, vol. 3 of SIAM Monographs on Discrete Mathematics and Applications. SIAM (1999)","DOI":"10.1137\/1.9780898719796"},{"issue":"1","key":"522_CR7","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s00026-001-8007-7","volume":"5","author":"G Brinkmann","year":"2001","unstructured":"Brinkmann, G., Koolen, J.H., Moulton, V.: On the hyperbolicity of chordal graphs. Ann. Combin. 5(1), 61\u201369 (2001)","journal-title":"Ann. Combin."},{"key":"522_CR8","doi-asserted-by":"crossref","unstructured":"Cohen, N., Coudert, D., Lancin, A.: On computing the Gromov hyperbolicity. ACM J. Exp. Algoritm. 20, 1.6:1\u20131.6:18 (2015)","DOI":"10.1145\/2780652"},{"key":"522_CR9","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.tcs.2017.06.001","volume":"690","author":"N Cohen","year":"2017","unstructured":"Cohen, N., Coudert, D., Ducoffe, G., Lancin, A.: Applying clique-decomposition for computing Gromov hyperbolicity. Theor. Comput. Sci. 690, 114\u2013139 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"522_CR10","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"DG Corneil","year":"1981","unstructured":"Corneil, D.G., Lerchs, H., Burlingham, L.S.: Complement reducible graphs. Discrete Appl. Math. 3(3), 163\u2013174 (1981)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"522_CR11","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"DG Corneil","year":"1985","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM J. Comput. 14(4), 926\u2013934 (1985)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"522_CR12","doi-asserted-by":"publisher","first-page":"1601","DOI":"10.1137\/140954787","volume":"28","author":"D Coudert","year":"2014","unstructured":"Coudert, D., Ducoffe, G.: Recognition of $$C_4$$ C 4 -free and 1\/2-hyperbolic graphs. SIAM J. Discrete Math. 28(3), 1601\u20131617 (2014)","journal-title":"SIAM J. Discrete Math."},{"key":"522_CR13","doi-asserted-by":"crossref","unstructured":"Coudert, D., Ducoffe, G., Popa, A.: Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. In: Proceedings of 29th SODA, pp. 2765\u20132784. SIAM (2018)","DOI":"10.1137\/1.9781611975031.176"},{"key":"522_CR14","doi-asserted-by":"crossref","unstructured":"Damaschke, P.: Induced subgraph isomorphism for cographs is NP-complete. In: Proceedings of 16th WG, vol. 484 of LNCS, pp. 72\u201378. Springer, Berlin (1991)","DOI":"10.1007\/3-540-53832-1_32"},{"key":"522_CR15","doi-asserted-by":"crossref","unstructured":"Doucha, M., Kratochv\u00edl, J.: Cluster vertex deletion: a parameterization between vertex cover and clique-width. In: Proceedings of the 37th MFCS, vol. 7464 of LNCS, pp. 348\u2013359. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-32589-2_32"},{"issue":"1\u20133","key":"522_CR16","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.tcs.2004.05.009","volume":"326","author":"F Eisenbrand","year":"2004","unstructured":"Eisenbrand, F., Grandoni, F.: On the complexity of fixed parameter clique and dominating set. Theor. Comput. Sci. 326(1\u20133), 57\u201367 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"522_CR17","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"M Fellows","year":"2009","unstructured":"Fellows, M., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"6\u20138","key":"522_CR18","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1016\/j.ipl.2015.02.002","volume":"115","author":"H Fournier","year":"2015","unstructured":"Fournier, H., Ismail, A., Vigneron, A.: Computing the Gromov hyperbolicity of a discrete metric space. Inf. Process. Lett. 115(6\u20138), 576\u2013579 (2015)","journal-title":"Inf. Process. Lett."},{"key":"522_CR19","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman (1979)"},{"key":"522_CR20","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."},{"key":"522_CR21","doi-asserted-by":"crossref","unstructured":"Gromov, M.: Hyperbolic groups. In: Essays in Group Theory, MSRI Publ., Vol. 8, pp. 75\u2013263. Springer, New York (1987)","DOI":"10.1007\/978-1-4613-9586-7_3"},{"issue":"1","key":"522_CR22","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.cosrev.2010.01.001","volume":"4","author":"M Habib","year":"2010","unstructured":"Habib, M., Paul, C.: A survey of the algorithmic aspects of modular decomposition. Comput. Sci. Rev. 4(1), 41\u201359 (2010)","journal-title":"Comput. Sci. Rev."},{"issue":"2","key":"522_CR23","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$ k -SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"522_CR24","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"522_CR25","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1006\/eujc.2002.0591","volume":"23","author":"JH Koolen","year":"2002","unstructured":"Koolen, J.H., Moulton, V.: Hyperbolic bridged graphs. Eur. J. Combin. 23(6), 683\u2013699 (2002)","journal-title":"Eur. J. Combin."},{"key":"522_CR26","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra","year":"1983","unstructured":"Lenstra, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"522_CR27","unstructured":"Mertzios, G.B., Nichterlein, A., Niedermeier, R.: The power of linear-time data reduction for maximum matching. In: Proceedings of 42nd MFCS, vol. 83 of LIPIcs, pp. 46:1\u201346:14. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik (2017)"},{"issue":"2","key":"522_CR28","doi-asserted-by":"crossref","first-page":"P2.39","DOI":"10.37236\/4053","volume":"21","author":"D Mitsche","year":"2014","unstructured":"Mitsche, D., Pralat, P.: On the hyperbolicity of random graphs. Electr. J. Combin. 21(2), P2.39 (2014)","journal-title":"Electr. J. Combin."},{"key":"522_CR29","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"CH Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Upper Saddle River (1982)"},{"key":"522_CR30","doi-asserted-by":"crossref","unstructured":"Williams, R., Yu, H.: Finding orthogonal vectors in discrete structures. In: Proceedings of 25th SODA, pp. 1867\u20131877. SIAM (2014)","DOI":"10.1137\/1.9781611973402.135"},{"key":"522_CR31","doi-asserted-by":"crossref","unstructured":"Williams, V.V., Wang, J.R., Williams, R., Yu, H.: Finding four-node subgraphs in triangle time. In: Proceedings of the 26th SODA, pp. 1671\u20131680. SIAM (2015)","DOI":"10.1137\/1.9781611973730.111"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0522-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0522-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0522-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:34:39Z","timestamp":1605227679000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0522-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,13]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["522"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0522-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,10,13]]},"assertion":[{"value":"9 April 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 October 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}