{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:46:12Z","timestamp":1725497172118},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540748380"},{"type":"electronic","value":"9783540748397"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"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":[[2007]]},"DOI":"10.1007\/978-3-540-74839-7_22","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T09:55:58Z","timestamp":1196934958000},"page":"226-237","source":"Crossref","is-referenced-by-count":5,"title":["Characterisations and Linear-Time Recognition of Probe Cographs"],"prefix":"10.1007","author":[{"given":"Van Bang","family":"Le","sequence":"first","affiliation":[]},{"given":"H. N.","family":"de Ridder","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"22_CR1","unstructured":"Bayer, D.: \u00dcber probe-trivially-perfect und probe-Cographen, Diplomarbeit, Universit\u00e4t Rostock, Institut f\u00fcr Informatik (2006)"},{"key":"22_CR2","unstructured":"Bayer, D., Van Bang Le, de Ridder, H.N.: Probe trivially perfect graphs and probe threshold graphs, Manuscript (2006)"},{"key":"22_CR3","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1137\/050637091","volume":"21","author":"A. Berry","year":"2007","unstructured":"Berry, A., Golumbic, M.C., Lipshteyn, M.: Recognizing chordal probe graphs and cycle-bicolorable graphs. SIAM J. Discrete Math.\u00a021, 573\u2013591 (2007)","journal-title":"SIAM J. Discrete Math."},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Van Bang Le, Spinrad, J.P.: Graph Classes: A Survey, Philadelphia. SIAM Monographs on Discrete Math. Appl., vol.\u00a03 (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"22_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/11775096_25","volume-title":"Algorithmic Aspects in Information and Management","author":"D.B. Chandler","year":"2006","unstructured":"Chandler, D.B., Chang, M.-S., Kloks, A.J.J., Liu, J., Peng, S.-L.: Recognition of probe cographs and partitioned probe distance hereditary graphs. In: Cheng, S.-W., Poon, C.K. (eds.) AAIM 2006. LNCS, vol.\u00a04041, pp. 267\u2013278. Springer, Heidelberg (2006)"},{"key":"22_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/11917496_17","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D.B. Chandler","year":"2006","unstructured":"Chandler, D.B., Chang, M.-S., Kloks, A.J.J., Liu, J., Peng, S.-L.: Partitioned probe comparability graphs. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 179\u2013190. Springer, Heidelberg (2006)"},{"key":"22_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1007\/11750321_47","volume-title":"Theory and Applications of Models of Computation","author":"D.B. Chandler","year":"2006","unstructured":"Chandler, D.B., Chang, M.-S., Kloks, A.J.J., Liu, J., Peng, S.-L.: On probe permutation graphs. In: Cai, J.-Y., Cooper, S.B., Li, A. (eds.) TAMC 2006. LNCS, vol.\u00a03959, pp. 494\u2013504. Springer, Heidelberg (2006)"},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"Chang, G.J., Kloks, A.J.J., Peng, S.-L.: Probe interval bigraphs. In: 2nd Brazilian Symposium on Graphs, Algorithms and Combinatorics (2005)","DOI":"10.1016\/j.endm.2005.05.027"},{"key":"22_CR9","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.J. Chang","year":"2005","unstructured":"Chang, G.J., Kloks, A.J.J., Liu, J., Peng, S.-L.: 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":"22_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1007\/11533719_82","volume-title":"Computing and Combinatorics","author":"M.-S. Chang","year":"2005","unstructured":"Chang, M.-S., Kloks, A.J.J., Kratsch, D., Liu, J., Peng, S.-L.: On the recognition of probe graphs of some self-complementary classes of perfect graphs. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 808\u2013817. Springer, Heidelberg (2005)"},{"key":"22_CR11","first-page":"249","volume":"43","author":"D.G. Corneil","year":"1984","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.: Cographs: recognition, application and algorithms. Congr. Numerantium\u00a043, 249\u2013258 (1984)","journal-title":"Congr. Numerantium"},{"key":"22_CR12","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"D.G. Corneil","year":"1985","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.: A linear recognition algorithm for cographs. SIAM J. Computing\u00a014, 926\u2013934 (1985)","journal-title":"SIAM J. Computing"},{"key":"22_CR13","doi-asserted-by":"publisher","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.: Chordal probe graphs. Discrete Appl. Math.\u00a0143, 221\u2013237 (2004)","journal-title":"Discrete Appl. Math."},{"key":"22_CR14","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/0095-8956(85)90050-4","volume":"39","author":"R.B. Hayward","year":"1985","unstructured":"Hayward, R.B.: Weakly triangulated graphs. J. Combin. Theory (B)\u00a039, 200\u2013209 (1985)","journal-title":"J. Combin. Theory (B)"},{"key":"22_CR15","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/BF01788666","volume":"5","author":"A. Hertz","year":"1989","unstructured":"Hertz, A.: Slim graphs. Graphs Comb.\u00a05, 149\u2013157 (1989)","journal-title":"Graphs Comb."},{"key":"22_CR16","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0012-365X(92)90134-2","volume":"105","author":"C.T. Ho\u00e0ng","year":"1992","unstructured":"Ho\u00e0ng, C.T., Maffray, F.: On slim graphs, even pairs, and star-cutsets. Discrete Math.\u00a0105, 93\u2013102 (1992)","journal-title":"Discrete Math."},{"key":"22_CR17","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1017\/S0963548300001826","volume":"5","author":"M. Hujter","year":"1996","unstructured":"Hujter, M., Tuza, Z.: Precoloring extensions III: Classes of perfect graphs. Comb. Prob. Comp.\u00a05, 35\u201356 (1996)","journal-title":"Comb. Prob. Comp."},{"key":"22_CR18","unstructured":"Information\u00a0System\u00a0on\u00a0Graph\u00a0Classes\u00a0and\u00a0their\u00a0Inclusions\u00a0(ISGCI), \n                  \n                    http:\/\/wwwteo.informatik.uni-rostock.de\/isgci"},{"key":"22_CR19","unstructured":"Johnson, J.L., Spinrad, J.P.: A polynomial time recognition algorithm for probe interval graphs. In: Proceedings ACM-SIAM symposium on discrete algorithms, pp. 477\u2013486 (2001)"},{"key":"22_CR20","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1002\/(SICI)1097-0118(199904)30:4<309::AID-JGT5>3.0.CO;2-5","volume":"30","author":"Bang Le","year":"1999","unstructured":"Van Bang Le: A good characterization of cograph contractions. J. Graph Theory\u00a030, 309\u2013318 (1999)","journal-title":"J. Graph Theory"},{"key":"22_CR21","unstructured":"Van Bang Le, de Ridder, H.N.: Probe split graphs. Discrete Mathematics and Theoretical Computer Science (to appear)"},{"key":"22_CR22","doi-asserted-by":"publisher","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.: On probe interval graphs. Discrete Appl. Math.\u00a088, 315\u2013324 (1998)","journal-title":"Discrete Appl. Math."},{"key":"22_CR23","unstructured":"McConnell, R.M., Spinrad, J.P.: Construction of probe interval models. In: Proceedings ACM-SIAM symposium on discrete algorithms, pp. 866\u2013875 (2002)"},{"key":"22_CR24","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.dam.2004.06.015","volume":"150","author":"N. Przulj","year":"2005","unstructured":"Przulj, N., Corneil, D.G.: 2-tree probe interval graphs have a large obstruction set. Discrete Appl. Math.\u00a0150, 216\u2013231 (2005)","journal-title":"Discrete Appl. Math."},{"key":"22_CR25","first-page":"33","volume":"140","author":"L. Sheng","year":"1999","unstructured":"Sheng, L.: Cycle free probe interval graphs. Congr. Numerantium\u00a0140, 33\u201342 (1999)","journal-title":"Congr. Numerantium"},{"key":"22_CR26","unstructured":"Zhang, P.: Probe interval graphs and its application to physical mapping of DNA (unpublished, 1994)"},{"key":"22_CR27","first-page":"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. Computer Applications in the Biosciences\u00a010, 309\u2013317 (1994)","journal-title":"Computer Applications in the Biosciences"},{"key":"22_CR28","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1002\/jgt.20002","volume":"46","author":"I.E. Zverovich","year":"2004","unstructured":"Zverovich, I.E., Zverovich, I.I.: Forbidden induced subgraph characterization of cograph contractions. J. Graph Theory\u00a046, 217\u2013226 (2004)","journal-title":"J. Graph Theory"}],"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_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T11:06:08Z","timestamp":1558263968000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74839-7_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540748380","9783540748397"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74839-7_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}