{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:56:29Z","timestamp":1725558989623},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_33","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"384-395","source":"Crossref","is-referenced-by-count":3,"title":["Interval Graphs: Canonical Representation in Logspace"],"prefix":"10.1007","author":[{"given":"Johannes","family":"K\u00f6bler","sequence":"first","affiliation":[]},{"given":"Sebastian","family":"Kuhnert","sequence":"additional","affiliation":[]},{"given":"Bastian","family":"Laubner","sequence":"additional","affiliation":[]},{"given":"Oleg","family":"Verbitsky","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"33_CR1","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1006\/jagm.1996.0058","volume":"21","author":"L. Babel","year":"1996","unstructured":"Babel, L., Ponomarenko, I.N., Tinhofer, G.: The isomorphism problem for directed path graphs and for rooted directed path graphs. J. Algorithms\u00a021(3), 542\u2013564 (1996)","journal-title":"J. Algorithms"},{"issue":"3","key":"33_CR2","doi-asserted-by":"crossref","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. J. Comput. Syst. Sci.\u00a013(3), 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"33_CR3","doi-asserted-by":"crossref","unstructured":"Datta, S., Limaye, N., Nimbhorkar, P., Thierauf, T., Wagner, F.: Planar graph isomorphism is in log-space. In: CCC, pp. 203\u2013214 (2009)","DOI":"10.1109\/CCC.2009.16"},{"issue":"3","key":"33_CR4","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jcss.1997.1485","volume":"54","author":"K. Etessami","year":"1997","unstructured":"Etessami, K.: Counting quantifiers, successor relations, and logarithmic space. Journal of Computer and System Sciences\u00a054(3), 400\u2013411 (1997)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"33_CR5","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D.R. Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pacific Journal of Mathematics\u00a015(3), 835\u2013855 (1965)","journal-title":"Pacific Journal of Mathematics"},{"issue":"1-2","key":"33_CR6","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M. Habib","year":"2000","unstructured":"Habib, M., McConnell, R.M., Paul, C., Viennot, L.: Lex-BFS and partition refinement. Theor. Comput. Sci.\u00a0234(1-2), 59\u201384 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"33_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-11493-9","volume-title":"Group-Theoretic Algorithms and Graph Isomorphism","author":"C.M. Hoffmann","year":"1982","unstructured":"Hoffmann, C.M.: Group-Theoretic Algorithms and Graph Isomorphism. LNCS, vol.\u00a0136. Springer, Heidelberg (1982)"},{"issue":"3","key":"33_CR8","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/S0097539792224814","volume":"28","author":"W.-L. Hsu","year":"1999","unstructured":"Hsu, W.-L., Ma, T.-H.: Fast and simple algorithms for recognizing chordal comparability graphs and interval graphs. SIAM J. Comput.\u00a028(3), 1004\u20131020 (1999)","journal-title":"SIAM J. Comput."},{"key":"33_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/11785293_7","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"H. Kaplan","year":"2006","unstructured":"Kaplan, H., Nussbaum, Y.: A simpler linear-time recognition of circular-arc graphs. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol.\u00a04059, pp. 41\u201352. Springer, Heidelberg (2006)"},{"issue":"4","key":"33_CR10","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1137\/S0097539789166880","volume":"25","author":"P.N. Klein","year":"1996","unstructured":"Klein, P.N.: Efficient parallel algorithms for chordal graphs. SIAM J. Comput.\u00a025(4), 797\u2013827 (1996)","journal-title":"SIAM J. Comput."},{"key":"33_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/978-3-642-03816-7_46","volume-title":"Mathematical Foundations of Computer Science 2009","author":"J. K\u00f6bler","year":"2009","unstructured":"K\u00f6bler, J., Kuhnert, S.: The isomorphism problem for k-trees is complete for logspace. In: Kr\u00e1lovi\u010d, R., Niwi\u0144ski, D. (eds.) MFCS 2009. LNCS, vol.\u00a05734, pp. 537\u2013548. Springer, Heidelberg (2009)"},{"key":"33_CR12","series-title":"Progress in Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0333-9","volume-title":"The Graph Isomorphism Problem: Its Structural Complexity","author":"J. K\u00f6bler","year":"1993","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Tor\u00e1n, J.: The Graph Isomorphism Problem: Its Structural Complexity. Progress in Theoretical Computer Science. Birkh\u00e4user, Basel (1993)"},{"key":"33_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1007\/3-540-16042-6_28","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"D. Kozen","year":"1985","unstructured":"Kozen, D., Vazirani, U.V., Vazirani, V.V.: NC algorithms for comparability graphs, interval gaphs, and testing for unique perfect matching. In: Maheshwari, S.N. (ed.) FSTTCS 1985. LNCS, vol.\u00a0206, pp. 496\u2013503. Springer, Heidelberg (1985)"},{"key":"33_CR14","doi-asserted-by":"crossref","unstructured":"Laubner, B.: Capturing polynomial time on interval graphs. In: LICS (to appear, 2010)","DOI":"10.1109\/LICS.2010.42"},{"key":"33_CR15","doi-asserted-by":"crossref","unstructured":"Lindell, S.: A logspace algorithm for tree canonization. In: STOC 1992, pp. 400\u2013404 (1992)","DOI":"10.1145\/129712.129750"},{"issue":"2","key":"33_CR16","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. J. ACM\u00a026(2), 183\u2013195 (1979)","journal-title":"J. ACM"},{"key":"33_CR17","series-title":"NATO ASI Series C, Mathematical and Physical Sciences","first-page":"41","volume-title":"Graphs and Order","author":"R.H. M\u00f6hring","year":"1984","unstructured":"M\u00f6hring, R.H.: Graphs and Order. NATO ASI Series C, Mathematical and Physical Sciences, vol.\u00a0147, pp. 41\u2013102. D. Reidel, Dordrecht (1984)"},{"issue":"2","key":"33_CR18","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1145\/62.322436","volume":"31","author":"J.H. Reif","year":"1984","unstructured":"Reif, J.H.: Symmetric complementation. J. ACM\u00a031(2), 401\u2013421 (1984)","journal-title":"J. ACM"},{"key":"33_CR19","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1145\/1060590.1060647","volume-title":"STOC","author":"O. Reingold","year":"2005","unstructured":"Reingold, O.: Undirected st-connectivity in log-space. In: STOC, pp. 376\u2013385. ACM, New York (2005)"},{"issue":"2","key":"33_CR20","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D.J. Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput.\u00a05(2), 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"key":"33_CR21","doi-asserted-by":"crossref","unstructured":"Spinrad, J.P.: Efficient graph representations. Field Institute Monographs, vol.\u00a019 (2003)","DOI":"10.1090\/fim\/019"},{"key":"33_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-540-77891-2_3","volume-title":"WALCOM: Algorithms and Computation","author":"R. Uehara","year":"2008","unstructured":"Uehara, R.: Simple geometrical intersection graphs. In: Nakano, S.-i., Rahman, M. S. (eds.) WALCOM 2008. LNCS, vol.\u00a04921, pp. 25\u201333. Springer, Heidelberg (2008)"},{"issue":"3","key":"33_CR23","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1093\/bioinformatics\/10.3.309","volume":"10","author":"P. Zhang","year":"1994","unstructured":"Zhang, P., Schon, E.A., Fischer, S.G., Cayanis, E., Weiss, J., Kistler, S., Bourne, P.E.: An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA. Bioinformatics\u00a010(3), 309\u2013317 (1994)","journal-title":"Bioinformatics"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T22:41:33Z","timestamp":1685659293000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}