{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:22Z","timestamp":1759638142840},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2009,7,1]],"date-time":"2009-07-01T00:00:00Z","timestamp":1246406400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2011,8]]},"DOI":"10.1007\/s10479-009-0584-6","type":"journal-article","created":{"date-parts":[[2009,6,30]],"date-time":"2009-06-30T13:47:17Z","timestamp":1246369637000},"page":"175-183","source":"Crossref","is-referenced-by-count":6,"title":["A characterization of chain probe graphs"],"prefix":"10.1007","volume":"188","author":[{"given":"Martin C.","family":"Golumbic","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fr\u00e9d\u00e9ric","family":"Maffray","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gr\u00e9gory","family":"Morel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,7,1]]},"reference":[{"key":"584_CR1","unstructured":"Berry, A., Golumbic, M. C., & Lipshteyn, M. (2004). Two tricks to triangulate chordal probe graphs in polynomial time. In Proc. SODA\u201904, 962\u2013969."},{"key":"584_CR2","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1137\/050637091","volume":"21","author":"A. Berry","year":"2007","unstructured":"Berry, A., Golumbic, M. C., & Lipshteyn, M. (2007). Cycle-bicolorable graphs and triangulating chordal probe graphs. SIAM Journal on Discrete Mathematics, 21, 573\u2013591.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"584_CR3","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V., & Spinrad, J. P. (1999) Graph classes: A survey. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia.","DOI":"10.1137\/1.9780898719796"},{"key":"584_CR4","doi-asserted-by":"crossref","unstructured":"Chandler, D. D., Chang, M.-S., Kloks, T., Le, V. B., & Peng, S.-L. (2008). Probe Ptolemaic graphs. In Proc. COCOON 2008. Lecture notes in computer science (Vol.\u00a05092, pp.\u00a0468\u2013477).","DOI":"10.1007\/978-3-540-69733-6_46"},{"key":"584_CR5","doi-asserted-by":"crossref","unstructured":"Chang, M.-S., Kloks, T., Kratsch, D., Liu, J., & Peng, S.-L. (2005). On the recognition of probe graphs of some self-complementary classes of perfect graphs. In Proc. COCOON 2005. Lecture notes in computer science (Vol.\u00a03595, pp.\u00a0808\u2013817).","DOI":"10.1007\/11533719_82"},{"key":"584_CR6","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/S0167-5060(08)70731-3","volume":"1","author":"V. Chv\u00e1tal","year":"1977","unstructured":"Chv\u00e1tal, V., & Hammer, P. (1977). Aggregation of inequalities integer programming. Annals of Discrete Mathematics, 1, 145\u2013162.","journal-title":"Annals of Discrete Mathematics"},{"key":"584_CR7","series-title":"Annals of discrete math.","volume-title":"Algorithmic graph theory and perfect graphs","author":"M. C. Golumbic","year":"2004","unstructured":"Golumbic, M. C. (2004). Algorithmic graph theory and perfect graphs (2nd edn.) Annals of discrete math., Vol.\u00a057. Amsterdam: Elsevier.","edition":"2"},{"key":"584_CR8","doi-asserted-by":"crossref","unstructured":"Golumbic, M. C., & Lipshteyn, M. (2003). Chordal probe graphs (extended abstract). In Proceedings of WG\u201903. Lecture notes in computer science (Vol.\u00a02880, pp.\u00a0249\u2013260).","DOI":"10.1007\/978-3-540-39890-5_22"},{"key":"584_CR9","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/j.dam.2003.12.009","volume":"143","author":"M. C. Golumbic","year":"2004","unstructured":"Golumbic, M. C., & Lipshteyn, M. (2004). Chordal probe graphs. Discrete Applied Mathematics, 143, 221\u2013237.","journal-title":"Discrete Applied Mathematics"},{"key":"584_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. (2004). Tolerance graphs. Cambridge: Cambridge University Press."},{"key":"584_CR11","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1006\/jagm.1995.1047","volume":"19","author":"M. C. Golumbic","year":"1995","unstructured":"Golumbic, M. C., Kaplan, H., & Shamir, R. (1995). Graph sandwich problems. Journal of Algorithms, 19, 449\u2013473.","journal-title":"Journal of Algorithms"},{"key":"584_CR12","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0166-218X(90)90092-Q","volume":"28","author":"P. L. Hammer","year":"1990","unstructured":"Hammer, P. L., Peled, U. N., & Sun, X. (1990). Difference graphs. Discrete Applied Mathematics, 28, 35\u201344.","journal-title":"Discrete Applied Mathematics"},{"key":"584_CR13","unstructured":"Johnson, J. L., & Spinrad, J. P. (2001). A polynomial time recognition algorithm for probe interval graphs. In Proc. 12th annual ACM-SIAM symp. on disc. algorithms (SODA) (pp.\u00a0477\u2013486)."},{"key":"584_CR14","first-page":"207","volume":"9","author":"V. B. Le","year":"2007","unstructured":"Le, V. B., & de Ridder, E. (2007a). Probe split graphs. Discrete Mathematics and Theoretical Computer Science, 9, 207\u2013238.","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"584_CR15","doi-asserted-by":"crossref","unstructured":"Le, V. B., & de Ridder, E. (2007b). Characterisations and linear-time recognition of probe cographs. In Proc. WG 2007. Lecture notes in computer science (Vol.\u00a04769, pp.\u00a0226\u2013237).","DOI":"10.1007\/978-3-540-74839-7_22"},{"key":"584_CR16","series-title":"Annals of discrete mathematics","volume-title":"Threshold graphs and related topics","author":"N. V. R. Mahadev","year":"1995","unstructured":"Mahadev, N. V. R., & Peled, U. N. (1995). Threshold graphs and related topics. Annals of discrete mathematics (Vol.\u00a056). Amsterdam: Elsevier."},{"key":"584_CR17","unstructured":"McConnell, R. M., & Spinrad, J. P. (2002). Construction of probe interval models. In Proc. 13th annual ACM-SIAM Symp. on disc. algorithms (SODA) (pp.\u00a0866\u2013875)."},{"key":"584_CR18","doi-asserted-by":"crossref","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. (1998). On probe interval graphs. Discrete Applied Mathematics, 88, 315\u2013324.","journal-title":"Discrete Applied Mathematics"},{"key":"584_CR19","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/j.dam.2004.06.015","volume":"150","author":"N. Przulj","year":"2005","unstructured":"Przulj, N., & Corneil, D. G. (2005). 2-Tree probe interval graphs have a large obstruction set. Discrete Applied Mathematics, 150, 216\u2013231.","journal-title":"Discrete Applied Mathematics"},{"key":"584_CR20","first-page":"33","volume":"140","author":"L. Sheng","year":"1999","unstructured":"Sheng, L. (1999). Cycle free probe interval graphs. Congressus Numerantium, 140, 33\u201342.","journal-title":"Congressus Numerantium"},{"key":"584_CR21","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M. (1981). Node-deletion problems on bipartite graphs. SIAM Journal on Computing, 10, 310\u2013327.","journal-title":"SIAM Journal on Computing"},{"key":"584_CR22","unstructured":"Zhang, P. (1994). Probe interval graphs and their application to physical mapping of DNA. Manuscript."},{"key":"584_CR23","first-page":"309","volume":"10","author":"P. Zhang","year":"1999","unstructured":"Zhang, P., Schon, E. A., Fischer, S. G. Cayanis, E. Weiss, J. Kistler, S. & Bourne, P.E. (1999a). An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA. CABIOS, 10, 309\u2013317.","journal-title":"CABIOS"},{"key":"584_CR24","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1006\/geno.1998.5631","volume":"55","author":"P. Zhang","year":"1999","unstructured":"Zhang, P., Ye, X., Liao, L., Russo, J., & Fischer, S. G. (1999b). Integrated mapping package\u2014a physical mapping software tool kit. Genomics, 55, 78\u201387.","journal-title":"Genomics"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-009-0584-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10479-009-0584-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-009-0584-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T14:07:55Z","timestamp":1559138875000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10479-009-0584-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7,1]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,8]]}},"alternative-id":["584"],"URL":"https:\/\/doi.org\/10.1007\/s10479-009-0584-6","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,7,1]]}}}