{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T14:31:41Z","timestamp":1791124301121,"version":"4.1.0"},"reference-count":38,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2004,1]]},"abstract":"<jats:p>In this paper, we study the complexity of recognizing powers of chordal graphs and its subclasses. We present the first polynomial time algorithm to recognize squares of proper interval graphs and give an outline of an algorithm to recognize kth powers of proper interval graphs for every natural number k. These are the first results of this type for a family of graphs that contains arbitrarily large cliques. On the other hand, we show the NP-completeness of recognizing squares of chordal graphs, recognizing squares of split graphs, and recognizing chordal graphs that are squares of some graph.<\/jats:p>","DOI":"10.1137\/s0895480103425930","type":"journal-article","created":{"date-parts":[[2004,7,22]],"date-time":"2004-07-22T21:00:37Z","timestamp":1090530037000},"page":"83-102","source":"Crossref","is-referenced-by-count":40,"title":["Recognizing Powers of Proper Interval, Split, and Chordal Graphs"],"prefix":"10.1137","volume":"18","author":[{"given":"Lap Chi","family":"Lau","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Derek G.","family":"Corneil","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1017\/S1446788700025696"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480193253415"},{"key":"R3","first-page":"161","volume":"67","author":"Chang Jou\u2010Ming","year":"2003","journal-title":"Ars Combin."},{"key":"R4","unstructured":"M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas,\n                      The Strong Perfect Graph Theorem\n                      , preprint. Available at http:\/\/www.math.gatech.edu\/\u223cthomas\/spgc.html."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2003.07.001"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90296-M"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792269095"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"PierreDuchet, Classical perfect graphs: an introduction with emphasis on triangulated and interval graphs, North\u2010Holland Math. Stud., Vol. 88, North\u2010Holland, Amsterdam, 1984, 67\u20139686b:05029","DOI":"10.1016\/S0304-0208(08)72924-4"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90074-4"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90091-4"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199704)24:4<323::AID-JGT4>3.3.CO;2-6"},{"key":"R12","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(68)80079-1"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1964-055-5"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(67)80050-4"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)90110-4"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700372216"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.9999"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359346"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90068-9"},{"key":"R21","unstructured":"H. T. Lau,\n                      Finding a Hamiltonian Cycle in the Square of a Block\n                      , Ph.D. thesis, School of Computer Science, McGill University, Montreal, QC, Canada, 1980."},{"key":"R22","unstructured":"L. C. Lau,\n                      Bipartite roots of graphs\n                      , in Proceedings of the 15th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2004, pp. 945\u2013954."},{"key":"R23","unstructured":"L. C. Lau,\n                      Roots of Graphs\n                      , Master\u2019s thesis, University of Toronto, Toronto, ON, Canada, 2003."},{"key":"R24","doi-asserted-by":"crossref","unstructured":"Guo\u2010HuiLin, PaulKearney, TaoJiang, Phylogenetick\u2010root and Steinerk\u2010root, Lecture Notes in Comput. Sci., Vol. 1969, Springer, Berlin, 2000, 539\u20135512002i:68094","DOI":"10.1007\/3-540-40996-3_46"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019120016X"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"R27","unstructured":"A. Lubiw,\n                      \u03b3\u2010free Matrices\n                      , Master\u2019s thesis, University of Waterloo, Waterloo, ON, Canada, 1982."},{"key":"R28","doi-asserted-by":"crossref","unstructured":"M. Molloy and M. R. Salavatipour,\n                      Frequency channel assignment on planar networks\n                      , in Proceedings of the 10th Annual European Symposium on Algorithms, Lecture Notes in Comput. Sci. 2461, Springer\u2010Verlag, Berlin, 2002, pp. 736\u2013747.","DOI":"10.1007\/3-540-45749-6_64"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00023-9"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(67)80030-9"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1195"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(78)90055-2"},{"key":"R33","first-page":"235","volume":"59","author":"Raychaudhuri Arundhati","year":"1987","journal-title":"Congr. Numer."},{"key":"R34","first-page":"147","volume":"34","author":"Raychaudhuri Arundhati","year":"1992","journal-title":"Ars Combin."},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1960.tb03936.x"},{"key":"R36","doi-asserted-by":"crossref","first-page":"265","DOI":"10.21136\/CPM.1963.117458","volume":"88","author":"Sekanina Milan","year":"1963","journal-title":"asopis P\u011best. Mat."},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90209-R"},{"key":"R38","volume-title":"Introduction to graph theory","author":"West Douglas","year":"1996"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895480103425930","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:20:16Z","timestamp":1787322016000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895480103425930"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["10.1137\/S0895480103425930"],"URL":"https:\/\/doi.org\/10.1137\/s0895480103425930","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,1]]}}}