{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:10:46Z","timestamp":1725541846633},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642114083"},{"type":"electronic","value":"9783642114090"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11409-0_25","type":"book-chapter","created":{"date-parts":[[2009,12,3]],"date-time":"2009-12-03T13:12:27Z","timestamp":1259845947000},"page":"285-295","source":"Crossref","is-referenced-by-count":1,"title":["A New Intersection Model and Improved Algorithms for Tolerance Graphs"],"prefix":"10.1007","author":[{"given":"George B.","family":"Mertzios","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shmuel","family":"Zaks","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-3","key":"25_CR1","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0166-218X(94)00044-E","volume":"60","author":"K.P. Bogart","year":"1995","unstructured":"Bogart, K.P., Fishburn, P.C., Isaak, G., Langley, L.: Proper and unit tolerance graphs. Discrete Applied Mathematics\u00a060(1-3), 99\u2013117 (1995)","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"25_CR2","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 triangle-free tolerance graphs. Discrete Applied Mathematics\u00a0154(3), 471\u2013477 (2006)","journal-title":"Discrete Applied Mathematics"},{"key":"25_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/978-3-540-74839-7_2","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A.H. Busch","year":"2007","unstructured":"Busch, A.H., Isaak, G.: Recognizing bipartite tolerance graphs in linear time. In: Brandst\u00e4dt, A., Kratsch, D., M\u00fcller, H. (eds.) WG 2007. LNCS, vol.\u00a04769, pp. 12\u201320. Springer, Heidelberg (2007)"},{"key":"25_CR4","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Berlin (2005)","edition":"3"},{"key":"25_CR5","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1002\/(SICI)1097-0118(199807)28:3<129::AID-JGT2>3.0.CO;2-M","volume":"28","author":"S. Felsner","year":"1998","unstructured":"Felsner, S.: Tolerance graphs and orders. Journal of Graph Theory\u00a028, 129\u2013140 (1998)","journal-title":"Journal of Graph Theory"},{"key":"25_CR6","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0166-218X(96)00013-3","volume":"74","author":"S. Felsner","year":"1997","unstructured":"Felsner, S., M\u00fcller, R., Wernisch, L.: Trapezoid graphs and generalizations, geometry and algorithms. Discrete Applied Mathematics\u00a074, 13\u201332 (1997)","journal-title":"Discrete Applied Mathematics"},{"key":"25_CR7","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0012-365X(98)00170-8","volume":"195","author":"P.C. Fishburn","year":"1999","unstructured":"Fishburn, P.C., Trotter, W.T.: Split semiorders. Discrete Mathematics\u00a0195, 111\u2013126 (1999)","journal-title":"Discrete Mathematics"},{"key":"25_CR8","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0012-365X(75)90103-X","volume":"11","author":"M.L. Fredman","year":"1975","unstructured":"Fredman, M.L.: On computing the length of longest increasing subsequences. Discrete Mathematics\u00a011, 29\u201335 (1975)","journal-title":"Discrete Mathematics"},{"key":"25_CR9","unstructured":"Golumbic, M.C., Monma, C.L.: A generalization of interval graphs with tolerances. In: Proceedings of the 13th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, vol.\u00a035, pp. 321\u2013331 (1982)"},{"issue":"2","key":"25_CR10","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 Mathematics\u00a09(2), 157\u2013170 (1984)","journal-title":"Discrete Applied Mathematics"},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C., Siani, A.: Coloring algorithms for tolerance graphs: Reasoning and scheduling with interval constraints. In: Joint International Conferences on Artificial Intelligence, Automated Reasoning, and Symbolic Computation (AISC\/Calculemus), pp. 196\u2013207 (2002)","DOI":"10.1007\/3-540-45470-5_19"},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"Golumbic, M., Trenk, A.: Tolerance Graphs. Cambridge Studies in Advanced Mathematics (2004)","DOI":"10.1017\/CBO9780511542985"},{"key":"25_CR13","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M. Gr\u00f6tshcel","year":"1981","unstructured":"Gr\u00f6tshcel, M., Lov\u00e1sz, L., Schrijver, A.: The Ellipsoid Method and its Consequences in Combinatorial Optimization. Combinatorica\u00a01, 169\u2013197 (1981)","journal-title":"Combinatorica"},{"issue":"1-3","key":"25_CR14","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 Applied Mathematics\u00a0143(1-3), 307\u2013311 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"25_CR15","unstructured":"Isaak, G., Nyman, K., Trenk, A.: A hierarchy of classes of bounded bitolerance orders. Ars Combinatoria\u00a069 (2003)"},{"issue":"1-3","key":"25_CR16","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.dam.2003.04.004","volume":"140","author":"J.M. Keil","year":"2004","unstructured":"Keil, J.M., Belleville, P.: Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs. Discrete Applied Mathematics\u00a0140(1-3), 73\u201389 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"25_CR17","unstructured":"Langley, L.: Interval tolerance orders and dimension. PhD thesis, Dartmouth College (June 1993)"},{"key":"25_CR18","series-title":"Society for Industrial and Applied Mathematics","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719802","volume-title":"Topics in Intersection Graph Theory","author":"T. McKee","year":"1999","unstructured":"McKee, T., McMorris, F.: Topics in Intersection Graph Theory. Society for Industrial and Applied Mathematics. SIAM, Philadelphia (1999)"},{"key":"25_CR19","doi-asserted-by":"crossref","unstructured":"Mertzios, G.B., Sau, I., Zaks, S.: A New Intersection Model and Improved Algorithms for Tolerance Graphs. Technical report, RWTH Aachen University (March 2009)","DOI":"10.1007\/978-3-642-11409-0_25"},{"key":"25_CR20","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0166-218X(92)90203-M","volume":"36","author":"G. Narasimhan","year":"1992","unstructured":"Narasimhan, G., Manber, R.: Stability and chromatic number of tolerance graphs. Discrete Applied Mathematics\u00a036, 47\u201356 (1992)","journal-title":"Discrete Applied Mathematics"}],"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-642-11409-0_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:40:20Z","timestamp":1606185620000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11409-0_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642114083","9783642114090"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11409-0_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}