{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:59:17Z","timestamp":1725559157073},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540241317"},{"type":"electronic","value":"9783540305514"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30551-4_73","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T14:15:37Z","timestamp":1279030537000},"page":"859-870","source":"Crossref","is-referenced-by-count":3,"title":["Canonical Data Structure for Interval Probe Graphs"],"prefix":"10.1007","author":[{"given":"Ryuhei","family":"Uehara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"73_CR1","volume-title":"Hypergraphs","author":"C. Berge","year":"1989","unstructured":"Berge, C.: Hypergraphs. Elsevier, Amsterdam (1989)"},{"key":"73_CR2","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-Tree Algorithms. Journal of Computer and System Sciences\u00a013, 335\u2013379 (1976)","journal-title":"Journal of Computer and System Sciences"},{"key":"73_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/978-3-540-39890-5_10","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A. Brandst\u00e4dt","year":"2003","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Le, H.-O., Van Le, B., Uehara, R.: Tree spanners for bipartite graphs and probe interval graphs. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 106\u2013118. Springer, Heidelberg (2003)"},{"key":"73_CR4","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)"},{"issue":"1","key":"73_CR5","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1137\/0210015","volume":"10","author":"C.J. Colbourn","year":"1981","unstructured":"Colbourn, C.J., Booth, K.S.: Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs. SIAM Journal on Computing\u00a010(1), 203\u2013225 (1981)","journal-title":"SIAM Journal on Computing"},{"key":"73_CR6","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":"73_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/978-3-540-39890-5_22","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M.C. Golumbic","year":"2003","unstructured":"Golumbic, M.C., Lipshteyn, M.: Chordal probe graphs. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 249\u2013260. Springer, Heidelberg (2003)"},{"key":"73_CR8","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C., Trenk, A.N.: Tolerance Graphs, Cambridge. Cambridge studies in advanced mathematics, vol.\u00a089 (2004)","DOI":"10.1017\/CBO9780511542985"},{"key":"73_CR9","unstructured":"Johnson, J.L., McConnell, R.M., Spinrad, J.P.: Linear Time Recognition of Probe Interval Graphs. In: preparation (2002)"},{"key":"73_CR10","first-page":"477","volume-title":"Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms","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 Ann. ACM-SIAM Symp. on Discrete Algorithms, pp. 477\u2013486. ACM, New York (2001)"},{"issue":"1","key":"73_CR11","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0218005","volume":"18","author":"N. Korte","year":"1989","unstructured":"Korte, N., M\u00f6hring, R.H.: An Incremental Linear-Time Algorithm for Recognizing Interval Graphs. SIAM Journal on Computing\u00a018(1), 68\u201381 (1989)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"73_CR12","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1145\/322123.322125","volume":"26","author":"G.S. Lueker","year":"1979","unstructured":"Lueker, G.S., Booth, K.S.: A Linear Time Algorithm for Deciding Interval Graph Isomorphism. Journal of the ACM\u00a026(2), 183\u2013195 (1979)","journal-title":"Journal of the ACM"},{"key":"73_CR13","first-page":"866","volume-title":"Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms","author":"R.M. McConnell","year":"2002","unstructured":"McConnell, R.M., Spinrad, J.P.: Construction of Probe Interval Models. In: Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms, pp. 866\u2013875. ACM, New York (2002)"},{"key":"73_CR14","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":"73_CR15","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. Discrete Applied Mathematics\u00a088, 315\u2013324 (1998)","journal-title":"Discrete Applied Mathematics"},{"key":"73_CR16","first-page":"955","volume-title":"Proc. 15th Ann. ACM-SIAM Symp. on Discrete Algorithms","author":"A. Nerry","year":"2004","unstructured":"Nerry, A., Golumbic, M.C., Lipshteyn, M.: Two Tricks to Triangulate Chordal Probe Graphs in Polynomial Time. In: Proc. 15th Ann. ACM-SIAM Symp. on Discrete Algorithms, pp. 955\u2013962. ACM, New York (2004)"},{"key":"73_CR17","volume-title":"Efficient Graph Representations","author":"J.P. Spinrad","year":"2003","unstructured":"Spinrad, J.P.: Efficient Graph Representations. American Mathematical Society, Providence (2003)"},{"key":"73_CR18","doi-asserted-by":"crossref","unstructured":"Uehara, R., Toda, S., Nagoya, T.: Graph Isomorphism Completeness for Chordal bipartite graphs and Strongly Chordal Graphs. Discrete Applied Mathematics (2004)(to apear)","DOI":"10.1016\/j.dam.2004.06.008"},{"key":"73_CR19","unstructured":"Zhang, P.: Probe Interval Graphs and Its Applications to Physical Mapping of DNA. manuscript (1994)"},{"key":"73_CR20","unstructured":"Zhang, P.: Probe Interval Graph and Its Applications to Physical Mapping of DNA. RECOMB 2000, Poster Session (2000), available at http:\/\/recomb2000.ims.u-tokyo.ac.jp\/Posters\/list-posters.html"},{"key":"73_CR21","unstructured":"Zhang, P.: United States Patent. Method of Mapping DNA Fragments. [Online] 5667970.htm, July 3 (2000), Available http:\/\/www.cc.columbia.edu\/cu\/cie\/techlists\/patents\/"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30551-4_73.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:21:33Z","timestamp":1605741693000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30551-4_73"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241317","9783540305514"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30551-4_73","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}