{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:13:24Z","timestamp":1725516804410},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540697329"},{"type":"electronic","value":"9783540697336"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69733-6_46","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"468-477","source":"Crossref","is-referenced-by-count":2,"title":["Probe Ptolemaic Graphs"],"prefix":"10.1007","author":[{"given":"David B.","family":"Chandler","sequence":"first","affiliation":[]},{"given":"Maw-Shang","family":"Chang","sequence":"additional","affiliation":[]},{"given":"Ton","family":"Kloks","sequence":"additional","affiliation":[]},{"given":"Van Bang","family":"Le","sequence":"additional","affiliation":[]},{"given":"Sheng-Lung","family":"Peng","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"46_CR1","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/0095-8956(86)90043-2","volume":"41","author":"H.J. Bandelt","year":"1986","unstructured":"Bandelt, H.J., Mulder, H.M.: Distance-Hereditary Graphs. Journal of Combinatorial Theory, Series B\u00a041, 182\u2013208 (1986)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"46_CR2","unstructured":"Bayer, D., Le, V.B., de Ridder, H.N.: Probe Trivially Perfect Graphs and Probe Threshold Graphs (manuscript) (2006)"},{"key":"46_CR3","unstructured":"Berry, A., Golumbic, M.C., Lipshteyn, M.: Two Tricks to Triangulate Chordal Probe Graphs in Polynomial Time. In: Proceedings of 15th ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 962\u2013969 (2004)"},{"key":"46_CR4","doi-asserted-by":"crossref","unstructured":"Br\u00e4ndstadt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. In: SIAM Monographs on Discrete Mathematics and Applications, Philadelphia (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"46_CR5","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":"46_CR6","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, T., 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":"46_CR7","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, T., 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":"46_CR8","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 \u2014 a Floor Show of Minimal Separators. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 521\u2013532. Springer, Heidelberg (2005)"},{"key":"46_CR9","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, T., Kratsch, D., Liu, J., Peng, S.-L.: On the Recognition of Probe Graphs of Some Self-complementary Graph Classes. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 808\u2013817. Springer, Heidelberg (2005)"},{"key":"46_CR10","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"D.G. Corneil","year":"1981","unstructured":"Corneil, D.G., Lerchs, H., Stewart, L.K.: Complement Reducible Graphs. Discrete Applied Mathematics\u00a03, 163\u2013174 (1981)","journal-title":"Discrete Applied Mathematics"},{"key":"46_CR11","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G.A. Dirac","year":"1961","unstructured":"Dirac, G.A.: On Rigid Circuit Graphs. Abh. Math. Sem. Univ. Hamburg\u00a025, 71\u201376 (1961)","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"key":"46_CR12","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1137\/0607049","volume":"7","author":"M. Farber","year":"1986","unstructured":"Farber, M., Jamison, R.E.: Convexity in Graphs and Hypergraphs. SIAM J. Alg. Discrete Methods\u00a07, 433\u2013444 (1986)","journal-title":"SIAM J. Alg. Discrete Methods"},{"key":"46_CR13","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.dam.2004.01.011","volume":"145","author":"M. Habib","year":"2005","unstructured":"Habib, M., Paul, C.: A Simple Linear Time Algorithm for Cograph Recognition. Discrete Applied Mathematics\u00a0145, 183\u2013197 (2005)","journal-title":"Discrete Applied Mathematics"},{"key":"46_CR14","first-page":"113","volume":"1","author":"A. Hajnal","year":"1958","unstructured":"Hajnal, A., Sur\u00e1nyi, J.: Uber die Aufl\u00f6sung von Graphen in Vollst\u00e4ndige Teilgraphen. Ann. Univ. Sci. Budapest, E\u00f6tv\u00f6s Sect. Math\u00a01, 113\u2013121 (1958)","journal-title":"Ann. Univ. Sci. Budapest, E\u00f6tv\u00f6s Sect. Math"},{"key":"46_CR15","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(90)90131-U","volume":"27","author":"P.L. Hammer","year":"1990","unstructured":"Hammer, P.L., Maffray, F.: Completely Separable Graphs. Discrete Applied Mathematics\u00a027, 85\u201399 (1990)","journal-title":"Discrete Applied Mathematics"},{"key":"46_CR16","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/S0304-3975(00)00005-0","volume":"259","author":"C.T. Ho\u00e0ng","year":"2001","unstructured":"Ho\u00e0ng, C.T., Sritharan, R.: Finding Houses and Holes in Graphs. Theoretical Computer Science\u00a0259, 233\u2013244 (2001)","journal-title":"Theoretical Computer Science"},{"key":"46_CR17","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1002\/jgt.3190050314","volume":"5","author":"E. Howorka","year":"1981","unstructured":"Howorka, E.: A Characterization of Ptolemaic Graphs. Journal of Graph Theory\u00a05, 323\u2013331 (1981)","journal-title":"Journal of Graph Theory"},{"key":"46_CR18","unstructured":"Johnson, J.L., Spinrad, J.: A Polynomial-Time Recognition Algorithm for Probe Interval Graphs. In: Proceedings of 12th ACM\u2013SIAM Symposium on Discrete Algorithms (SODA 2001), pp. 447\u2013486 (2001)"},{"key":"46_CR19","doi-asserted-by":"crossref","first-page":"342","DOI":"10.4153\/CJM-1965-034-0","volume":"17","author":"D.C. Kay","year":"1965","unstructured":"Kay, D.C., Chartrand, G.: A Characterization of Certain Ptolemaic Graphs. Canad. J. Math.\u00a017, 342\u2013346 (1965)","journal-title":"Canad. J. Math."},{"key":"46_CR20","first-page":"207","volume":"9","author":"V.B. Le","year":"2007","unstructured":"Le, V.B., de Ridder, H.N.: Probe Split Graphs. Discrete Mathematics and Theoretical Computer Science\u00a09, 207\u2013238 (2007)","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"46_CR21","doi-asserted-by":"crossref","unstructured":"Le, V.B., de Ridder, H.N.: Characterizations and Linear-Time Recognition for Probe Cographs. LNCS, vol.\u00a04769, pp. 226\u2013237 (2007)","DOI":"10.1007\/978-3-540-74839-7_22"},{"key":"46_CR22","unstructured":"McConnell, R.M., Spinrad, J.P.: Construction of Probe Interval Graphs. In: Proceedings 13th ACM\u2013SIAM Symposium on Discrete Algorithms (SODA 2002), pp. 866\u2013875 (2002)"},{"key":"46_CR23","first-page":"257","volume":"19","author":"R.H. M\u00f6hring","year":"1984","unstructured":"M\u00f6hring, R.H., Radermacher, F.J.: Substitution Decomposition for Discrete Structures and Connections with Combinatorial Optimization. Ann. Discrete Math.\u00a019, 257\u2013356 (1984)","journal-title":"Ann. Discrete Math."},{"key":"46_CR24","unstructured":"Nicolai, F.: Strukturelle und Algorithmische Aspekte Distanz-erblicher Graphen und Verwandter Klasses. Dissertation thesis, Gerhard-Mercator-Universit\u00e4t, Duisburg (1994)"},{"key":"46_CR25","unstructured":"de Ridder, H.N.: On Probe Graph Classes. PhD thesis, Universit\u00e4t Rostock, Germany (2007)"},{"key":"46_CR26","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D.J. Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic Aspects of Vertex Elimination on Graph. SIAM Journal of Computing\u00a05, 266\u2013283 (1976)","journal-title":"SIAM Journal of Computing"},{"key":"46_CR27","first-page":"419","volume":"28","author":"V.P. Soltan","year":"1983","unstructured":"Soltan, V.P.: d-Convexity in Graphs. Soviet Math. Dokl.\u00a028, 419\u2013421 (1983)","journal-title":"Soviet Math. Dokl."},{"key":"46_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/11602613_20","volume-title":"Algorithms and Computation","author":"R. Uehara","year":"2005","unstructured":"Uehara, R., Uno, Y.: Laminar Structure of Ptolemaic and its Applications. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 186\u2013195. Springer, Heidelberg (2005)"},{"key":"46_CR29","doi-asserted-by":"publisher","first-page":"789","DOI":"10.2307\/2034179","volume":"13","author":"E.S. Wolk","year":"1962","unstructured":"Wolk, E.S.: The Comparability Graph of a Tree. Proceedings of the American Mathematical Society\u00a013, 789\u2013795 (1962)","journal-title":"Proceedings of the American Mathematical Society"},{"key":"46_CR30","doi-asserted-by":"publisher","first-page":"17","DOI":"10.2307\/2033992","volume":"16","author":"E.S. Wolk","year":"1965","unstructured":"Wolk, E.S.: A Note on The Comparability Graph of a Tree. Proceedings of the American Mathematical Society\u00a016, 17\u201320 (1965)","journal-title":"Proceedings of the American Mathematical Society"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69733-6_46.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:02:18Z","timestamp":1605762138000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69733-6_46"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540697329","9783540697336"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69733-6_46","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}