{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T13:34:41Z","timestamp":1726407281570},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540434009"},{"type":"electronic","value":"9783540459958"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45995-2_22","type":"book-chapter","created":{"date-parts":[[2007,5,30]],"date-time":"2007-05-30T02:33:34Z","timestamp":1180492414000},"page":"209-223","source":"Crossref","is-referenced-by-count":0,"title":["On the Power of BFS to Determine a Graphs Diameter"],"prefix":"10.1007","author":[{"given":"Derek G.","family":"Corneil","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feodor F.","family":"Dragan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ekkehard","family":"K\u00f6hler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,3,14]]},"reference":[{"key":"22_CR1","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1137\/S0097539796303421","volume":"28","author":"D. Aingworth","year":"1999","unstructured":"D. Aingworth, C. Chekuri, P. Indyk and R. Motwani, Fast estimation of diameter and shortest paths (without matrix multiplication), SIAM J. on Computing, 28 (1999), 1167\u20131181.","journal-title":"SIAM J. on Computing"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progression, Proceedings of the 19th ACM Symposium on Theory of Computing, 1987, 1\u20136.","DOI":"10.1145\/28395.28396"},{"key":"22_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/BFb0049406","volume-title":"Linear-time algorithm for finding a central vertex of a chordal graph","author":"V.D. Chepoi","year":"1994","unstructured":"V.D. Chepoi and F.F. Dragan, Linear-time algorithm for finding a central vertex of a chordal graph, \u201cAlgorithms-ESA\u201994 \u201d Second Annual European Symposium, Utrecht, The Netherlands, September 1994, Springer, LNCS 855 (Jan van Leeuwen, ed.), (1994), 159\u2013170."},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/S0166-218X(00)00281-X","volume":"113","author":"D.G. Corneil","year":"2001","unstructured":"D.G. Corneil, F.F. Dragan, M. Habib and C. Paul, Diameter determination on restricted graph families, Discrete Appl. Math., 113 (2001), 143\u2013166.","journal-title":"Discrete Appl. Math."},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"1284","DOI":"10.1137\/S0097539795282377","volume":"28","author":"D.G. Corneil","year":"1999","unstructured":"D.G. Corneil, S. Olariu and L. Stewart, Linear time algorithms for dominating pairs in asteroidal triple-free graphs, SIAM J. on Computing, 28 (1999), 1284\u20131297.","journal-title":"SIAM J. on Computing"},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"D. Dor, S. Halperin, and U. Zwick, All pairs almost shortest paths, Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 1996, 452\u2013461.","DOI":"10.1109\/SFCS.1996.548504"},{"key":"22_CR7","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/S0166-218X(99)00077-3","volume":"95","author":"F.F. Dragan","year":"1999","unstructured":"F.F. Dragan, Almost diameter of a house-hole-free graph in linear time via LexBFS, Discrete Appl. Math., 95 (1999), 223\u2013239.","journal-title":"Discrete Appl. Math."},{"key":"22_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1007\/3-540-62559-3_15","volume-title":"LexBFS-orderings and powers of graphs","author":"F.F. Dragan","year":"1997","unstructured":"F.F. Dragan, F. Nicolai and A. Brandst\u00e4dt, LexBFS-orderings and powers of graphs, Proc. of the WG\u201996, LNCS 1197, (1997), 166\u2013180."},{"key":"22_CR9","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1287\/trsc.7.3.287","volume":"7","author":"G. Handler","year":"1973","unstructured":"G. Handler, Minimax location of a facility in an undirected tree graph, Transportation Sciences, 7 (1973), 287\u2013293.","journal-title":"Transportation Sciences"},{"key":"22_CR10","doi-asserted-by":"publisher","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C.G. Lekkerkerker","year":"1962","unstructured":"C.G. Lekkerkerker and J.C. Boland, Representation of a finite graph by a set of intervals on the real line, Fundamenta Mathematicae, 51 (1962), 45\u201364.","journal-title":"Fundamenta Mathematicae"},{"key":"22_CR11","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D. Rose","year":"1976","unstructured":"D. Rose, R.E. Tarjan and G. Lueker, Algorithmic aspects on vertex elimination on graphs, SIAM J. on Computing, 5 (1976), 266\u2013283.","journal-title":"SIAM J. on Computing"},{"key":"22_CR12","doi-asserted-by":"crossref","unstructured":"R. Seidel, On the all-pair-shortest-path problem, Proceedings of the 24th ACM Symposium on Theory of Computing, 1992, 745\u2013749.","DOI":"10.1145\/129712.129784"},{"key":"22_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/3-540-44676-1_3","volume-title":"Exact and Approximate Distances in Graphs-A survey","author":"U. Zwick","year":"2001","unstructured":"Uri Zwick, Exact and Approximate Distances in Graphs-A survey, \u201cAlgorithms-ESA\u201901 \u201d 9th Annual European Symposium, Aarhus, Denmark, August 2001, Springer, LNCS 2161, (2001), 33\u201348."}],"container-title":["Lecture Notes in Computer Science","LATIN 2002: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45995-2_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,17]],"date-time":"2019-02-17T00:51:10Z","timestamp":1550364670000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45995-2_22"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540434009","9783540459958"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-45995-2_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2002]]}}}