{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T08:25:43Z","timestamp":1725524743195},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540791270"},{"type":"electronic","value":"9783540791287"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79128-7_18","type":"book-chapter","created":{"date-parts":[[2009,2,9]],"date-time":"2009-02-09T11:01:46Z","timestamp":1234177306000},"page":"313-322","source":"Crossref","is-referenced-by-count":1,"title":["Probe Interval Orders"],"prefix":"10.1007","author":[{"given":"David E.","family":"Brown","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Larry J.","family":"Langley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"unstructured":"Berry, A., Golumbic, M., & Lipshteyn, M. (2004). Two tricks to triangulate chordal probe graphs in polynomial time. In Proc. of the 12th ACM-SIAM symp. on discrete algorithms (SODA04). Association for Computing Machinery.","key":"18_CR1_18"},{"key":"18_CR2_18","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0097-3165(76)90004-2","volume":"21","author":"K. Bogart","year":"1976","unstructured":"Bogart, K., Rabinovitch, I., & Trotter, W.T. (1976). A bound on the dimension of interval orders. Journal of Combinatorial Theory A, 21, 219\u2013238.","journal-title":"Journal of Combinatorial Theory A"},{"key":"18_CR3_18","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"J. Boland","year":"1962","unstructured":"Boland, J. & Lekkerkerker, C. (1962). Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae, 51, 45\u201364.","journal-title":"Fundamenta Mathematicae"},{"unstructured":"Brown, D. & Langley, L. (2006). Probe interval graphs and orders. In Thirty-Sixth International Southeastern Conference on Combinatorics, Graph Theory, and Computing.","key":"18_CR4_18"},{"key":"18_CR5_18","first-page":"221","volume":"35","author":"D. Brown","year":"2006","unstructured":"Brown, D. & Lundgren, J. (2006). Bipartite probe interval graphs, interval point bigraphs, and circular arc graphs. Australasian Journal of Combinatorics, 35, 221\u2013236.","journal-title":"Australasian Journal of Combinatorics"},{"key":"18_CR6_18","first-page":"5","volume":"156","author":"D. Brown","year":"2002","unstructured":"Brown, D., Lundgren, J., & Flink, S. (2002). Interval k-graphs. Congressus Numerantium, 156, 5\u201316.","journal-title":"Congressus Numerantium"},{"unstructured":"Brown, D., Lundgren, J., & Sheng, L. (2008). Cycle-free unit and proper probe interval graphs. submitted to Discrete Applied Math.","key":"18_CR7_18"},{"doi-asserted-by":"crossref","unstructured":"Brown D. E., Lundgren, J. R., & Sheng, L., A characterization of cycle-free unit probe interval graphs, Discrete Applied Mathematics (2008), doi:10.1016\/j.dam.2008.07.004","key":"18_CR8_18","DOI":"10.1016\/j.dam.2008.07.004"},{"issue":"1","key":"18_CR9_18","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.dam.2004.06.015","volume":"150","author":"D. Corneil","year":"2005","unstructured":"Corneil, D. & Pr\u017eulj, N. (2005). 2-tree probe interval graphs have a large obstruction set. Discrete Applied Mathematics, 150(1), 216\u2013231","journal-title":"Discrete Applied Mathematics"},{"key":"18_CR10_18","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/0022-2496(70)90062-3","volume":"7","author":"P. C. Fishburn","year":"1970","unstructured":"Fishburn, P. C. (1970). Intransitive indifference with unequal indifference intervals. Journal of Mathematical Psychology, 7, 144\u2013149.","journal-title":"Journal of Mathematical Psychology"},{"key":"18_CR11_18","volume-title":"Interval orders and interval graphs","author":"P. C. Fishburn","year":"1985","unstructured":"Fishburn, P. C. (1985). Interval orders and interval graphs. New York: Wiley."},{"key":"18_CR12_18","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D. Fulkerson","year":"1965","unstructured":"Fulkerson, D. & Gross, O. (1965). Incidence matrices and interval graphs. Pacific Journal of Mathematics, 15, 835\u2013855.","journal-title":"Pacific Journal of Mathematics"},{"key":"18_CR13_18","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T. Gallai","year":"1967","unstructured":"Gallai, T. (1967). Transitiv orientbare graphen. Acta Mathematica Academiae Scientiarum Hun-garicae, 18, 25\u201366.","journal-title":"Acta Mathematica Academiae Scientiarum Hun-garicae"},{"key":"18_CR14_18","volume-title":"Algorithmic graph theory and perfect graphs","author":"M. Golumbic","year":"1980","unstructured":"Golumbic, M. (1980). Algorithmic graph theory and perfect graphs. New York: Academic."},{"key":"18_CR15_18","first-page":"97","volume":"153","author":"M. Golumbic","year":"2001","unstructured":"Golumbic, M. & Lipshteyn, M. (2001). On the hierarchy of interval, probe, and tolerance graphs. Congressus Numerantium, 153, 97\u2013106.","journal-title":"Congressus Numerantium"},{"key":"18_CR16_18","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/j.dam.2003.12.009","volume":"143","author":"M. Golumbic","year":"2004","unstructured":"Golumbic, M. & Lipshteyn, M. (2004). Chordal probe graphs. Discrete Applied Mathematics, 143, 221\u2013237.","journal-title":"Discrete Applied Mathematics"},{"key":"18_CR17_18","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0166-218X(84)90016-7","volume":"9","author":"M. Golumbic","year":"1984","unstructured":"Golumbic, M., Monma, C., & Totter, W. (1984). Tolerance graphs. Discrete Applied Mathematics, 9, 157\u2013170.","journal-title":"Discrete Applied Mathematics"},{"doi-asserted-by":"crossref","unstructured":"Golumbic, M. & Trenk, A. (2004). Tolerance graphs. Cambridge: Cambridge University Press. Greenough, T. (1974). Representation and enumeration of interval orders and semiorders. Dartmouth College.","key":"18_CR18_18","DOI":"10.1017\/CBO9780511542985"},{"key":"18_CR19_18","first-page":"477","volume-title":"Proc. of the 12th ACM-SIAM symp. on discrete algorithms (SODA01)","author":"J. Johnson","year":"2001","unstructured":"Johnson, J. & Spinrad, J. (2001). A polynomial time recognition algorithm for probe interval graphs. Proc. of the 12th ACM-SIAM symp. on discrete algorithms (SODA01) (pp. 477\u2013486). New York, NY: Association for Computing Machinery."},{"key":"18_CR20_18","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0166-218X(94)00056-J","volume":"60","author":"L. Langley","year":"1995","unstructured":"Langley, L. (1995). A recognition algorithm for orders of interval dimension two. Discrete Applied Mathematics, 60, 257\u2013266.","journal-title":"Discrete Applied Mathematics"},{"unstructured":"Lipshteyn, M. (2001). Probe graphs. Unpublished master's thesis, Bar-Ilan University.","key":"18_CR21_18"},{"doi-asserted-by":"crossref","unstructured":"McConnell, M. (2001). Linear-time recognition of circular-arc graphs. In Proc. of the 42nd annual IEEE symposium on foundations of computer science (FOCS 01) (pp. 386\u2013394).","key":"18_CR22_18","DOI":"10.1109\/SFCS.2001.959913"},{"key":"18_CR23_18","first-page":"866","volume-title":"Proc. of the 13th ACM-SIAM symposium on discrete algs. (SODA02)","author":"R. McConnell","year":"2002","unstructured":"McConnell, R. & Lundgren, J. (2002). Construction of probe interval models. Proc. of the 13th ACM-SIAM symposium on discrete algs. (SODA02) (pp. 866\u2013875). San Francisco, CA: Association for Computing Machinery."},{"key":"18_CR24_18","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"R. McConnell","year":"1999","unstructured":"McConnell, R. & Spinrad, J. (1999). Modular decomposition and transitive orientation. Discrete Mathematics, 201, 189\u2013241.","journal-title":"Discrete Mathematics"},{"key":"18_CR25_18","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/S0166-218X(98)00077-8","volume":"88","author":"F. McMorris","year":"1998","unstructured":"McMorris, F., Wang, C., & Zhang, P. (1998). On probe interval graphs. Discrete Applied Mathematics, 88, 315\u2013324.","journal-title":"Discrete Applied Mathematics"},{"unstructured":"Mirkin, B. G. (1970). Ob odnom klasse otnoshenij predpochtenija. Matematitcheskije woprosy formirovanija economitcheskich modelei.","key":"18_CR26_18"},{"key":"18_CR27_18","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0022-2496(72)90030-2","volume":"9","author":"B. G. Mirkin","year":"1972","unstructured":"Mirkin, B. G. (1972). Description of some relations on the set of real-line intervals. Journal of Mathematical Psychology, 9, 243\u2013252.","journal-title":"Journal of Mathematical Psychology"},{"key":"18_CR28_18","volume-title":"Discrete mathematical models","author":"F. Roberts","year":"1976","unstructured":"Roberts, F. (1976). Discrete mathematical models. Upper Saddle River, NJ: Prentice-Hall."},{"key":"18_CR29_18","first-page":"33","volume":"88","author":"L. Sheng","year":"1999","unstructured":"Sheng, L. (1999). Cycle-free probe interval graphs. Congressus Numerantium, 88, 33\u201342.","journal-title":"Congressus Numerantium"},{"unstructured":"Zhang, P. (1994). Probe interval graph and its applications to physical mapping of DNA. (Manuscript)","key":"18_CR30_18"},{"unstructured":"Zhang, P. (1997). Methods of mapping DNA fragments. (United States Patent. \n                      http:\/\/www.cc. columbia.edu\/cu\/cie\/techlists\/patents\/5667970.htm\n                      \n                    )","key":"18_CR31_18"},{"issue":"3","key":"18_CR32_18","first-page":"309","volume":"10","author":"P. Zhang","year":"1994","unstructured":"Zhang, P., Schon, E., Fischer, S., Cayanis, E., Weiss, J., Kistler, S., et al. (1994). An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA. CABIOS, 10(3), 309\u2013317.","journal-title":"CABIOS"}],"container-title":["Studies in Choice and Welfare","The Mathematics of Preference, Choice and Order"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79128-7_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:11:28Z","timestamp":1619521888000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79128-7_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540791270","9783540791287"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79128-7_18","relation":{},"ISSN":["1614-0311"],"issn-type":[{"type":"print","value":"1614-0311"}],"subject":[]}}