{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:04:28Z","timestamp":1758265468894,"version":"3.40.3"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030174019"},{"type":"electronic","value":"9783030174026"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-17402-6_5","type":"book-chapter","created":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T13:37:00Z","timestamp":1558359420000},"page":"50-61","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Parameterized Complexity of Diameter"],"prefix":"10.1007","author":[{"given":"Matthias","family":"Bentert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Nichterlein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,6]]},"reference":[{"key":"5_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: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pp. 377\u2013391. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch28"},{"issue":"4","key":"5_CR2","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1137\/S0097539796303421","volume":"28","author":"D Aingworth","year":"1999","unstructured":"Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28(4), 1167\u20131181 (1999)","journal-title":"SIAM J. Comput."},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"Backurs, A., Roditty, L., Segal, G., Williams, V.V., Wein, N.: Towards tight approximation bounds for graph diameter and eccentricities. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), pp. 267\u2013280. ACM (2018)","DOI":"10.1145\/3188745.3188950"},{"key":"5_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-662-55751-8_9","volume-title":"Fundamentals of Computation Theory","author":"M Bentert","year":"2017","unstructured":"Bentert, M., Fluschnik, T., Nichterlein, A., Niedermeier, R.: Parameterized aspects of triangle enumeration. In: Klasing, R., Zeitoun, M. (eds.) FCT 2017. LNCS, vol. 10472, pp. 96\u2013110. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-55751-8_9"},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.tcs.2015.02.033","volume":"586","author":"M Borassi","year":"2015","unstructured":"Borassi, M., Crescenzi, P., Habib, M., Kosters, W.A., Marino, A., Takes, F.W.: Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs: with an application to the six degrees of separation games. Theor. Comput. Sci. 586, 59\u201380 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"Borassi, M., Crescenzi, P., Trevisan, L.: An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pp. 920\u2013939. SIAM (2017)","DOI":"10.1137\/1.9781611974782.58"},{"key":"5_CR7","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, vol. 3. SIAM, Philadelphia (1999)"},{"issue":"4","key":"5_CR8","doi-asserted-by":"publisher","first-page":"1277","DOI":"10.1137\/060664690","volume":"22","author":"A Bretscher","year":"2008","unstructured":"Bretscher, A., Corneil, D.G., Habib, M., Paul, C.: A simple linear time LexBFS cograph recognition algorithm. SIAM J. Discret. Math. 22(4), 1277\u20131296 (2008)","journal-title":"SIAM J. Discret. Math."},{"key":"5_CR9","unstructured":"Bringmann, K., Husfeldt, T., Magnusson, M.: Multivariate analysis of orthogonal range searching and graph distances parameterized by treewidth. Computing Research Repository abs\/1805.07135 (2018). Accepted at IPEC 2018"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"Cairo, M., Grossi, R., Rizzi, R.: New bounds for approximating external distances in undirected graphs. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pp. 363\u2013376. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch27"},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Williams, R.: Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pp. 1246\u20131255. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch87"},{"issue":"4","key":"5_CR12","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."},{"key":"5_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 the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 2765\u20132784. SIAM (2018)","DOI":"10.1137\/1.9781611975031.176"},{"key":"5_CR14","unstructured":"Evald, J., Dahlgaard, S.: Tight hardness results for distance and centrality problems in constant degree graphs. Computing Research Repository abs\/1609.08403 (2016)"},{"key":"5_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/978-3-319-62127-2_34","volume-title":"Algorithms and Data Structures","author":"T Fluschnik","year":"2017","unstructured":"Fluschnik, T., Komusiewicz, C., Mertzios, G.B., Nichterlein, A., Niedermeier, R., Talmon, N.: When can graph hyperbolicity be computed in linear time? Algorithms and Data Structures. LNCS, vol. 10389, pp. 397\u2013408. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-62127-2_34"},{"issue":"3","key":"5_CR16","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. Algorithms 14(3), 34:1\u201334:45 (2018)","journal-title":"ACM Trans. Algorithms"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Kaplan, H., Mozes, S., Sharir, M., Weimann, O.: Voronoi diagrams on planar graphs, and computing the diameter in deterministic \u00d5(n$${}^{\\text{5\/3}}$$) time. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 495\u2013514. SIAM (2018)","DOI":"10.1137\/1.9781611975031.33"},{"key":"5_CR18","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":"12","key":"5_CR19","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"M Girvan","year":"2002","unstructured":"Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99(12), 7821\u20137826 (2002)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"5_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-540-28639-4_15","volume-title":"Parameterized and Exact Computation","author":"J Guo","year":"2004","unstructured":"Guo, J., H\u00fcffner, F., Niedermeier, R.: A structural view on parameterizing problems: distance from triviality. In: Downey, R., Fellows, M., Dehne, F. (eds.) IWPEC 2004. LNCS, vol. 3162, pp. 162\u2013173. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-28639-4_15"},{"issue":"2","key":"5_CR21","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-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"5_CR22","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":"1","key":"5_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321992.321993","volume":"24","author":"DB Johnson","year":"1977","unstructured":"Johnson, D.B.: Efficient algorithms for shortest paths in sparse networks. J. ACM 24(1), 1\u201313 (1977)","journal-title":"J. ACM"},{"key":"5_CR24","unstructured":"Korenwein, V., Nichterlein, A., Niedermeier, R., Zschoche, P.: Data reduction for maximum matching on real-world graphs: theory and experiments. In: Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018). LIPIcs, vol. 112. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)"},{"key":"5_CR25","unstructured":"Kratsch, S., Nelles, F.: Efficient and adaptive parameterized algorithms on modular decompositions. In: Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018). LIPIcs, vol. 112, pp. 55:1\u201355:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018)"},{"key":"5_CR26","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Horvitz, E.: Planetary-scale views on a large instant-messaging network. In: Proceedings of the 17th International World Wide Web Conference (WWW 2008), pp. 915\u2013924. ACM (2008). ISBN 978-1-60558-085-2","DOI":"10.1145\/1367497.1367620"},{"key":"5_CR27","unstructured":"Mertzios, G.B., Nichterlein, A., Niedermeier, R.: The power of linear-time data reduction for maximum matching. In: Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). LIPIcs, vol. 83, pp. 46:1\u201346:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)"},{"key":"5_CR28","first-page":"61","volume":"1","author":"S Milgram","year":"1967","unstructured":"Milgram, S.: The small world problem. Psychol. Today 1, 61\u201367 (1967)","journal-title":"Psychol. Today"},{"issue":"2","key":"5_CR29","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1137\/S003614450342480","volume":"45","author":"MEJ Newman","year":"2003","unstructured":"Newman, M.E.J.: The structure and function of complex networks. SIAM Rev. 45(2), 167\u2013256 (2003)","journal-title":"SIAM Rev."},{"key":"5_CR30","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks: An Introduction","author":"MEJ Newman","year":"2010","unstructured":"Newman, M.E.J.: Networks: An Introduction. Oxford University Press, Oxford (2010)"},{"issue":"3","key":"5_CR31","doi-asserted-by":"publisher","first-page":"036122","DOI":"10.1103\/PhysRevE.68.036122","volume":"68","author":"MEJ Newman","year":"2003","unstructured":"Newman, M.E.J., Park, J.: Why social networks are different from other types of networks. Phys. Rev. E 68(3), 036122 (2003)","journal-title":"Phys. Rev. E"},{"key":"5_CR32","doi-asserted-by":"crossref","unstructured":"Roditty, L., Williams, V.V.: Fast approximation algorithms for the diameter and radius of sparse graphs. In: Proceedings of the 45th Symposium on Theory of Computing Conference (STOC 2013), pp. 515\u2013524. ACM (2013)","DOI":"10.1145\/2488608.2488673"},{"issue":"3","key":"5_CR33","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jcss.1995.1078","volume":"51","author":"R Seidel","year":"1995","unstructured":"Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. J. Comput. Syst. Sci. 51(3), 400\u2013403 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"5_CR34","unstructured":"Sorge, M., Weller, M.: The graph parameter hierarchy (2013, manuscript)"},{"issue":"1","key":"5_CR35","doi-asserted-by":"crossref","first-page":"12:1","DOI":"10.1145\/2764910","volume":"12","author":"O Weimann","year":"2016","unstructured":"Weimann, O., Yuster, R.: Approximating the diameter of planar graphs in near linear time. ACM Trans. Algorithms 12(1), 12:1\u201312:13 (2016)","journal-title":"ACM Trans. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-17402-6_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T16:27:22Z","timestamp":1710347242000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-17402-6_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030174019","9783030174026"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-17402-6_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"6 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rome","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 May 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 May 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/easyconferences.eu\/ciac2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"95","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"14","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}