{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T13:12:26Z","timestamp":1742994746417,"version":"3.40.3"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319123394"},{"type":"electronic","value":"9783319123400"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-12340-0_30","type":"book-chapter","created":{"date-parts":[[2014,10,20]],"date-time":"2014-10-20T04:27:23Z","timestamp":1413779243000},"page":"360-371","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Polynomial Time Recognition of Squares of Ptolemaic Graphs and 3-sun-free Split Graphs"],"prefix":"10.1007","author":[{"given":"Van Bang","family":"Le","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Oversberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oliver","family":"Schaudt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,10,21]]},"reference":[{"key":"30_CR1","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1137\/100792949","volume":"24","author":"A Adamszek","year":"2010","unstructured":"Adamszek, A., Adamszek, M.: Large-girth roots of graphs. SIAM J. Discrete Math. 24, 1501\u20131514 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"30_CR2","doi-asserted-by":"crossref","first-page":"139","DOI":"10.37236\/626","volume":"18","author":"A Adamszek","year":"2011","unstructured":"Adamszek, A., Adamszek, M.: Uniqueness of graph square roots of girth six. Electron. J. Combin. 18, 139 (2011)","journal-title":"Electron. J. Combin."},{"key":"30_CR3","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0012-365X(94)00052-K","volume":"145","author":"H-J Bandelt","year":"1995","unstructured":"Bandelt, H.-J., Henkmann, A., Nicolai, F.: Powers of distance-hereditary graphs. Disc. Math. 145, 37\u201360 (1995)","journal-title":"Disc. Math."},{"key":"30_CR4","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. J. Combin. Theory (Ser. B) 41, 182\u2013208 (1986)","journal-title":"J. Combin. Theory (Ser. B)"},{"key":"30_CR5","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM, Philadelphia (1999)"},{"key":"30_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/11785293_38","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"M-S Chang","year":"2006","unstructured":"Chang, M.-S., Ko, M.-T., Lu, H.-I.: Linear-time algorithms for tree root problems. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, pp. 411\u2013422. Springer, Heidelberg (2006)"},{"key":"30_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-45043-3_16","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M Cochefert","year":"2013","unstructured":"Cochefert, M., Couturier, J.-F., Golovach, P.A., Kratsch, D., Paulusma, D.: Sparse square roots. In: Brandst\u00e4dt, A., Jansen, K., Reischuk, R. (eds.) WG 2013. LNCS, vol. 8165, pp. 177\u2013188. Springer, Heidelberg (2013)"},{"key":"30_CR8","unstructured":"Dalhaus, E., Duchet, P.: On strongly chordal graphs. Ars Combin. 24B, 23\u201330 (1987)"},{"key":"30_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/jcd.20179","volume":"17","author":"MC Dourado","year":"2009","unstructured":"Dourado, M.C., Protti, F., Szwarcfiter, J.L.: Complexity aspects of the helly property: graphs and hypergraphs. Electron. J. Combin. 17, 1\u201353 (2009)","journal-title":"Electron. J. Combin."},{"key":"30_CR10","unstructured":"Farzad, B., Karimi, M.: Square-root finding problem in graphs, a complete dichotomy theorem, arXiv:1210.7684 (2012)"},{"key":"30_CR11","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/s00453-010-9442-9","volume":"62","author":"B Farzad","year":"2012","unstructured":"Farzad, B., Lau, L.C., Le, V.B., Tuy, N.N.: Complexity of finding graph roots with girth conditions. Algorithmica 62, 38\u201353 (2012)","journal-title":"Algorithmica"},{"key":"30_CR12","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(90)90131-U","volume":"27","author":"PL Hammer","year":"1990","unstructured":"Hammer, P.L., Maffray, F.: Completely separable graphs. Disc. App. Math. 27, 85\u201399 (1990)","journal-title":"Disc. App. Math."},{"key":"30_CR13","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. J. Graph Theory 5, 323\u2013331 (1981)","journal-title":"J. Graph Theory"},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1145\/1150334.1150337","volume":"2","author":"LC Lau","year":"2006","unstructured":"Lau, L.C.: Bipartite roots of graphs. ACM Trans. Algorithms 2, 178\u2013208 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"30_CR15","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1137\/S0895480103425930","volume":"18","author":"LC Lau","year":"2004","unstructured":"Lau, L.C., Corneil, D.G.: Recognizing powers of proper interval, split, and chordal graphs. SIAM J. Discrete Math. 18, 83\u2013102 (2004)","journal-title":"SIAM J. Discrete Math."},{"key":"30_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/978-3-642-11409-0_21","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"VB Le","year":"2010","unstructured":"Le, V.B., Nguyen, N.T.: Hardness results and efficient algorithms for graph powers. In: Paul, C., Habib, M. (eds.) WG 2009. LNCS, vol. 5911, pp. 238\u2013249. Springer, Heidelberg (2010)"},{"key":"30_CR17","doi-asserted-by":"publisher","first-page":"734","DOI":"10.1016\/j.disc.2009.09.004","volume":"310","author":"VB Le","year":"2010","unstructured":"Le, V.B., Tuy, N.N.: The square of a block graph. Disc. Math. 310, 734\u2013741 (2010)","journal-title":"Disc. Math."},{"key":"30_CR18","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.ipl.2010.11.003","volume":"310","author":"VB Le","year":"2011","unstructured":"Le, V.B., Tuy, N.N.: A good characterization of squares of strongly chordal split graphs. Inf. Process. Lett. 310, 120\u2013123 (2011)","journal-title":"Inf. Process. Lett."},{"key":"30_CR19","doi-asserted-by":"publisher","first-page":"854","DOI":"10.1137\/0216057","volume":"16","author":"A Lubiw","year":"1987","unstructured":"Lubiw, A.: Doubly lexical orderings of matrices. SIAM J. Comput. 16, 854\u2013879 (1987)","journal-title":"SIAM J. Comput."},{"key":"30_CR20","doi-asserted-by":"publisher","first-page":"1538","DOI":"10.1016\/j.dam.2012.12.027","volume":"161","author":"M Milani\u010d","year":"2013","unstructured":"Milani\u010d, M., Schaudt, O.: Computing square roots of trivially perfect and threshold graphs. Disc. App. Math. 161, 1538\u20131545 (2013)","journal-title":"Disc. App. Math."},{"key":"30_CR21","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0166-218X(94)00023-9","volume":"54","author":"R Motwani","year":"1994","unstructured":"Motwani, R., Sudan, M.: Computing roots of graphs is hard. Disc. App. Math. 54, 81\u201388 (1994)","journal-title":"Disc. App. Math."},{"key":"30_CR22","first-page":"216","volume":"14","author":"E Prisner","year":"1993","unstructured":"Prisner, E.: Hereditary clique-Helly graphs. J. Comb. Math. Comb. Comput. 14, 216\u2013220 (1993)","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"30_CR23","first-page":"147","volume":"34","author":"A Raychaudhuri","year":"1992","unstructured":"Raychaudhuri, A.: On powers of strongly chordal and circular arc graphs. Ars Combin. 34, 147\u2013160 (1992)","journal-title":"Ars Combin."},{"key":"30_CR24","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6, 505\u2013517 (1977)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12340-0_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T04:16:32Z","timestamp":1675829792000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-12340-0_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319123394","9783319123400"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12340-0_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"21 October 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}