{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:32:22Z","timestamp":1725564742069},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540204527"},{"type":"electronic","value":"9783540398905"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39890-5_10","type":"book-chapter","created":{"date-parts":[[2010,9,4]],"date-time":"2010-09-04T01:16:57Z","timestamp":1283563017000},"page":"106-118","source":"Crossref","is-referenced-by-count":4,"title":["Tree Spanners for Bipartite Graphs and Probe Interval Graphs"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Brandst\u00e4dt","sequence":"first","affiliation":[]},{"given":"Feodor F.","family":"Dragan","sequence":"additional","affiliation":[]},{"given":"Hoang-Oanh","family":"Le","sequence":"additional","affiliation":[]},{"given":"Van Bang","family":"Le","sequence":"additional","affiliation":[]},{"given":"Ryuhei","family":"Uehara","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","unstructured":"Awerbuch, B., Baratz, A., Peleg, D.: Efficient broadcast and light-weighted spanners (1992) (manuscript)"},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-8858(86)90038-2","volume":"7","author":"H.-J. Bandelt","year":"1986","unstructured":"Bandelt, H.-J., Dress, A.: Reconstructing the Shape of a Tree from Observed Dissimilarity Data. Advances in Applied Mathematics\u00a07, 309\u2013343 (1986)","journal-title":"Advances in Applied Mathematics"},{"issue":"1","key":"10_CR3","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1006\/jagm.1998.0962","volume":"30","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Chepoi, V., Dragan, F.: Distance Approximating Trees for Chordal and Dually Chordal Graphs. J. of Algorithms\u00a030(1), 166\u2013184 (1999)","journal-title":"J. of Algorithms"},{"key":"10_CR4","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0166-218X(97)00125-X","volume":"82","author":"A. Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Chepoi, V.D., Dragan, F.F.: The Algorithmic Use of Hypertree Structure and Maximum Neighbourhood Orderings. Disc. Appl. Math.\u00a082, 43\u201377 (1998)","journal-title":"Disc. Appl. Math."},{"issue":"3","key":"10_CR5","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1137\/S0895480193253415","volume":"11","author":"A. Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Dragan, F., Chepoi, V., Voloshin, V.: Dually Chordal Graphs. SIAM J. Disc. Math.\u00a011(3), 437\u2013455 (1998)","journal-title":"SIAM J. Disc. Math."},{"key":"10_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/3-540-36136-7_15","volume-title":"Algorithms and Computation","author":"A. Brandst\u00e4dt","year":"2002","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Le, H.-O., Le, V.B.: Tree Spanners on Chordal Graphs: Complexity, Algorithms, Open Problems. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol.\u00a02518, pp. 163\u2013174. Springer, Heidelberg (2002)"},{"key":"10_CR7","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM, Philadelphia (1999)"},{"key":"10_CR8","first-page":"65","volume":"88","author":"L. Cai","year":"1992","unstructured":"Cai, L., Corneil, D.G.: Tree Spanners: an Overview. Congressus Numerantium\u00a088, 65\u201376 (1992)","journal-title":"Congressus Numerantium"},{"issue":"3","key":"10_CR9","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S0895480192237403","volume":"8","author":"L. Cai","year":"1995","unstructured":"Cai, L., Corneil, D.G.: Tree Spanners. SIAM J. Disc. Math.\u00a08(3), 359\u2013387 (1995)","journal-title":"SIAM J. Disc. Math."},{"key":"10_CR10","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0166-218X(95)00070-8","volume":"68","author":"F.F. Dragan","year":"1996","unstructured":"Dragan, F.F., Voloshin, V.I.: Incidence Graphs of Biacyclic Hypergraphs. Disc. Appl. Math.\u00a068, 259\u2013266 (1996)","journal-title":"Disc. Appl. Math."},{"key":"10_CR11","volume-title":"Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"10_CR12","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, London (1980)"},{"key":"10_CR13","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1002\/jgt.3190020209","volume":"2","author":"M.C. Golumbic","year":"1978","unstructured":"Golumbic, M.C., Goss, C.F.: Perfect Elimination and Chordal Bipartite Graphs. J. of Graph Theory\u00a02, 155\u2013163 (1978)","journal-title":"J. of Graph Theory"},{"key":"10_CR14","first-page":"739","volume":"23","author":"F. Harary","year":"1982","unstructured":"Harary, F., Kabell, J.A., McMorris, F.R.: Bipartite intersection graphs. Comment. Math. Univ. Carolin.\u00a023, 739\u2013745 (1982)","journal-title":"Comment. Math. Univ. Carolin."},{"key":"10_CR15","first-page":"477","volume-title":"Proc. 12th SODA","author":"J.L. Johnson","year":"2001","unstructured":"Johnson, J.L., Spinrad, J.P.: A Polynomial Time Recognition Algorithm for Probe Interval Graphs. In: Proc. 12th SODA, pp. 477\u2013486. ACM, New York (2001)"},{"key":"10_CR16","unstructured":"K\u00f6nig, D.: Theorie der endlichen und unendlichen Graphen. Akademische Verlagsgesellschaft (1936) (in German)"},{"key":"10_CR17","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1002\/(SICI)1097-0037(199909)34:2<81::AID-NET1>3.0.CO;2-P","volume":"34","author":"H.-O. Le","year":"1999","unstructured":"Le, H.-O., Le, V.B.: Optimal Tree 3-Spanners in Directed Path Graphs. Networks\u00a034, 81\u201387 (1999)","journal-title":"Networks"},{"key":"10_CR18","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0020-0190(96)00078-6","volume":"59","author":"M.S. Madanlal","year":"1996","unstructured":"Madanlal, M.S., Venkatesan, G., Rangan, C.P.: Tree 3-Spanners on Interval, Permutation and Regular Bipartite Graphs. IPL\u00a059, 97\u2013102 (1996)","journal-title":"IPL"},{"key":"10_CR19","first-page":"866","volume-title":"Proc. 13th SODA","author":"R.M. McConnell","year":"2002","unstructured":"McConnell, R.M., Spinrad, J.P.: Construction of Probe Interval Models. In: Proc. 13th SODA, pp. 866\u2013875. ACM, New York (2002)"},{"key":"10_CR20","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719802","volume-title":"Topics in Intersection Graph Theory","author":"T.A. McKee","year":"1999","unstructured":"McKee, T.A., McMorris, F.R.: Topics in Intersection Graph Theory. SIAM, Philadelphia (1999)"},{"key":"10_CR21","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/S0166-218X(98)00077-8","volume":"88","author":"F.R. McMorris","year":"1998","unstructured":"McMorris, F.R., Wang, C., Zhang, P.: On Probe Interval Graphs. Disc. Appl. Math.\u00a088, 315\u2013324 (1998)","journal-title":"Disc. Appl. Math."},{"key":"10_CR22","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0166-218X(97)00027-9","volume":"78","author":"H. M\u00fcller","year":"1997","unstructured":"M\u00fcller, H.: Recognizing Interval Digraphs and Interval Bigraphs in Polynomial Time. Disc. Appl. Math.\u00a078, 189\u2013205 (1997), Erratum is available at \n                    \n                      http:\/\/www.comp.leeds.ac.uk\/hm\/pub\/node1.html","journal-title":"Disc. Appl. Math."},{"key":"10_CR23","series-title":"Monographs on Discrete Mathematics and Applications","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locally-Sensitive Approach","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locally-Sensitive Approach. Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (2000)"},{"issue":"1","key":"10_CR24","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph Spanners. J. of Graph Theory\u00a013(1), 99\u2013116 (1989)","journal-title":"J. of Graph Theory"},{"key":"10_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0023484","volume-title":"STACS 97","author":"E. Prisner","year":"1997","unstructured":"Prisner, E.: Distance approximating spanning trees. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol.\u00a01200, Springer, Heidelberg (1997)"},{"key":"10_CR26","first-page":"225","volume":"89","author":"J. Soares","year":"1992","unstructured":"Soares, J.: Graph Spanners: a Survey. Congress Numerantium\u00a089, 225\u2013238 (1992)","journal-title":"Congress Numerantium"},{"key":"10_CR27","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1006\/inco.1997.2641","volume":"136","author":"G. Venkatesan","year":"1997","unstructured":"Venkatesan, G., Rotics, U., Madanlal, M.S., Makowsy, J.A., Rangan, C.P.: Restrictions of Minimum Spanner Problems. Inf. and Comp.\u00a0136, 143\u2013164 (1997)","journal-title":"Inf. and Comp."},{"key":"10_CR28","unstructured":"Zhang, P.: Probe Interval Graphs and Its Applications to Physical Mapping of DNA (1994) (manuscript)"},{"key":"10_CR29","unstructured":"Zhang, P.: United States Patent. Method of Mapping DNA Fragments (July 3, 2000), [Online] Available \n                    \n                      http:\/\/www.cc.columbia.edu\/cu\/cie\/techlists\/patents\/5667970.htm"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39890-5_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,19]],"date-time":"2019-03-19T20:49:50Z","timestamp":1553028590000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39890-5_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540204527","9783540398905"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39890-5_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}