{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:46:08Z","timestamp":1725497168992},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540748380"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74839-7_2","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T14:55:58Z","timestamp":1196952958000},"page":"12-20","source":"Crossref","is-referenced-by-count":2,"title":["Recognizing Bipartite Tolerance Graphs in Linear Time"],"prefix":"10.1007","author":[{"given":"Arthur H.","family":"Busch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Garth","family":"Isaak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"Booth, K., Lueker, G.: Linear Algorithms to Recognize Interval Graphs and Test for the Consecutive Ones Property. In: Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, pp. 255\u2013265 (1975)","DOI":"10.1145\/800116.803776"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes, A Survey. Soc. for Industrial and Applied Math., Philadelphia, PA (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"2_CR3","first-page":"165","volume":"58","author":"A. Brandst\u00e4dt","year":"1987","unstructured":"Brandst\u00e4dt, A., Spinrad, J.P., Stewart, L.: Bipartite permutation graphs are bipartite tolerance graphs. Congress. Numer.\u00a058, 165\u2013174 (1987)","journal-title":"Congress. Numer."},{"key":"2_CR4","unstructured":"Brown, D.E.: Variations on Interval Graphs, Ph.D. thesis, University of Colorado at Denver (2004)"},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1016\/j.dam.2005.06.010","volume":"154","author":"A.H. Busch","year":"2006","unstructured":"Busch, A.H.: A characterization of bipartite tolerance graphs. Discrete Applied Math.\u00a0154, 471\u2013477 (2006)","journal-title":"Discrete Applied Math."},{"key":"2_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1007\/978-3-540-31856-9_43","volume-title":"STACS 2005","author":"G. Chang","year":"2005","unstructured":"Chang, G., Kloks, A., Liu, J., Peng, S.: The PIGS Full Monty - A Floor Show of Minimal Separators. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 521\u2013532. Springer, Heidelberg (2005)"},{"key":"2_CR7","unstructured":"Derigs, U., Goecke, O., Schrader, R.: Bisimplicial edges, gaussian elimination and matchings in bipartite graphs. In: Inter. Workshop on Graph-Theoretic Concepts in Comp. Sci., pp. 79\u201387 (1984)"},{"key":"2_CR8","first-page":"321","volume":"35","author":"M.C. Golumbic","year":"1982","unstructured":"Golumbic, M.C., Monma, C.L.: A generalization of interval graphs with tolerances. Congress. Numer.\u00a035, 321\u2013331 (1982)","journal-title":"Congress. Numer."},{"key":"2_CR9","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0166-218X(84)90016-7","volume":"9","author":"M.C. Golumbic","year":"1984","unstructured":"Golumbic, M.C., Monma, C.L., Trotter, W.T.: Tolerance Graphs. Discrete Applied Math.\u00a09, 157\u2013170 (1984)","journal-title":"Discrete Applied Math."},{"key":"2_CR10","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511542985","volume-title":"Tolerance Graphs","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C., Trenk, A.N.: Tolerance Graphs. Cambridge University Press, Cambridge, UK (2004)"},{"key":"2_CR11","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/j.dam.2003.08.012","volume":"143","author":"R.B. Hayward","year":"2004","unstructured":"Hayward, R.B., Shamir, R.: A note on tolerance graph recognition. Discrete Appl. Math.\u00a0143, 307\u2013311 (2004)","journal-title":"Discrete Appl. Math."},{"key":"2_CR12","unstructured":"Langley, L.: Interval tolerance orders and dimension, Ph.D. thesis, Dartmouth College (1993)"},{"key":"2_CR13","doi-asserted-by":"publisher","first-page":"854","DOI":"10.1137\/0216057","volume":"16","author":"A. Lubiw","year":"1987","unstructured":"Lubiw, A.: Doubly lexical orderings of matrices. Siam J. Comput.\u00a016, 854\u2013879 (1987)","journal-title":"Siam J. Comput."},{"key":"2_CR14","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. Discrete Appl. Math.\u00a078, 189\u2013205 (1997)","journal-title":"Discrete Appl. Math."},{"key":"2_CR15","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R. Paige","year":"1987","unstructured":"Paige, R., Tarjan, R.E.: Three partition refinements of algorithms. SIAM J. Comput.\u00a016, 973\u2013989 (1987)","journal-title":"SIAM J. Comput."},{"key":"2_CR16","first-page":"33","volume":"140","author":"L. Sheng","year":"1999","unstructured":"Sheng, L.: Cycle free probe interval graphs. Congr. Numer.\u00a0140, 33\u201342 (1999)","journal-title":"Congr. Numer."},{"key":"2_CR17","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0020-0190(93)90209-R","volume":"45","author":"J.P. Spinrad","year":"1993","unstructured":"Spinrad, J.P.: Doubly lexical ordering of dense 0-1 matrices. Inf. Proc. Lett.\u00a045, 229\u2013235 (1993)","journal-title":"Inf. Proc. Lett."},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"18","author":"J.P. Spinrad","year":"1987","unstructured":"Spinrad, J.P., Brandst\u00e4dt, A., Stewart, L.: Bipartite permutation graphs. Discrete Appl. Math.\u00a018, 279\u2013292 (1987)","journal-title":"Discrete Appl. Math."},{"key":"2_CR19","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R.E. Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth-First Search and Linear Graph Algorithms. SIAM J. Comput.\u00a01, 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"key":"2_CR20","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(72)90019-6","volume":"12","author":"A.C. Tucker","year":"1972","unstructured":"Tucker, A.C.: A Structure Theorem for the Consecutive 1\u2019s Property. J. Combinatorial Theory Ser. B\u00a012, 153\u2013162 (1972)","journal-title":"J. Combinatorial Theory Ser. B"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74839-7_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:42:32Z","timestamp":1619520152000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74839-7_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540748380"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74839-7_2","relation":{},"subject":[]}}