{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T17:37:06Z","timestamp":1725817026910},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319156118"},{"type":"electronic","value":"9783319156125"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-15612-5_9","type":"book-chapter","created":{"date-parts":[[2015,2,23]],"date-time":"2015-02-23T04:05:18Z","timestamp":1424664318000},"page":"89-100","source":"Crossref","is-referenced-by-count":0,"title":["Approximate Distance Oracle in O(n2) Time and O(n) Space for Chordal Graphs"],"prefix":"10.1007","author":[{"given":"Gaurav","family":"Singh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N. S.","family":"Narayanaswamy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G.","family":"Ramakrishna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"9_CR1","volume-title":"Introduction to algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., et al.: Introduction to algorithms, vol.\u00a02. MIT Press, Cambridge (2001)"},{"issue":"3","key":"9_CR2","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. Journal of Computer and System Sciences\u00a051(3), 400\u2013403 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Williams, V.V.: Multiplying matrices faster than coppersmith-winograd. In: Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, pp. 887\u2013898. ACM (2012)","DOI":"10.1145\/2213977.2214056"},{"issue":"1","key":"9_CR4","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0166-218X(96)00103-5","volume":"77","author":"K. Han","year":"1997","unstructured":"Han, K., Sekharan, C.N., Sridhar, R.: Unified all-pairs shortest path algorithms in the chordal hierarchy. Discrete Applied Mathematics\u00a077(1), 59\u201371 (1997)","journal-title":"Discrete Applied Mathematics"},{"key":"9_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1007\/3-540-44676-1_40","volume-title":"Algorithms - ESA 2001","author":"C. Gavoille","year":"2001","unstructured":"Gavoille, C., Katz, M., Katz, N.A., Paul, C., Peleg, D.: Approximate distance labeling schemes. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 476\u2013487. Springer, Heidelberg (2001)"},{"issue":"1","key":"9_CR6","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1002\/net.3230220103","volume":"22","author":"R. Ravi","year":"1992","unstructured":"Ravi, R., Marathe, M.V., Pandu Rangan, C.: An optimal algorithm to solve the all-pair shortest path problem on interval graphs. Networks\u00a022(1), 21\u201335 (1992)","journal-title":"Networks"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Radhakrishnan, V., Hunt, H., Stearns, R.: On Solving Systems of Linear Equations and Path Problems for Bounded Treewidth Graphs. State University of New York at Albany, Department of Computer Science (1992)","DOI":"10.1007\/3-540-55210-3_177"},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/3-540-56402-0_36","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"E. Dahlhaus","year":"1993","unstructured":"Dahlhaus, E.: Optimal (parallel) algorithms for the all-to-all vertices distance problem for certain graph classes. In: Mayr, E.W. (ed.) WG 1992. LNCS, vol.\u00a0657, pp. 60\u201369. Springer, Heidelberg (1993)"},{"issue":"1","key":"9_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M. Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. Journal of the ACM (JACM)\u00a052(1), 1\u201324 (2005)","journal-title":"Journal of the ACM (JACM)"},{"key":"9_CR10","unstructured":"Cohen, E., Zwick, U.: All-pairs small-stretch paths. In: Proceedings of the eighth annual ACM-SIAM Symposium on Discrete algorithms, pp. 93\u2013102. Society for Industrial and Applied Mathematics (1997)"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Baswana, S., Kavitha, T.: Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In: 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, pp. 591\u2013602. IEEE (2006)","DOI":"10.1109\/FOCS.2006.29"},{"issue":"3","key":"9_CR12","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1002\/jgt.3190120313","volume":"12","author":"Y. Shibata","year":"1988","unstructured":"Shibata, Y.: On the tree representation of chordal graphs. Journal of Graph Theory\u00a012(3), 421\u2013428 (1988)","journal-title":"Journal of Graph Theory"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic graph theory and perfect graphs, vol.\u00a02. Elsevier (2004)","DOI":"10.1016\/S0167-5060(04)80059-1"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Blair, J.R., Peyton, B.: An introduction to chordal graphs and clique trees. In: Graph Theory and Sparse Matrix Computation, pp. 1\u201329. Springer (1993)","DOI":"10.1007\/978-1-4613-8369-7_1"},{"issue":"2","key":"9_CR15","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 Journal on Computing\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"9_CR16","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"Schieber, B., Vishkin, U.: On finding lowest common ancestors: simplification and parallelization. SIAM Journal on Computing\u00a017(6), 1253\u20131262 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"9_CR17","unstructured":"Powell, P.: A further improved LCA algorithm. Technical report TR90-01. University of Minnesota, Institute of Technology, Computer Science Department (1990)"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-15612-5_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T10:21:46Z","timestamp":1559125306000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-15612-5_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319156118","9783319156125"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-15612-5_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}