{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:32Z","timestamp":1759638092474},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642114083"},{"type":"electronic","value":"9783642114090"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11409-0_21","type":"book-chapter","created":{"date-parts":[[2009,12,3]],"date-time":"2009-12-03T13:12:27Z","timestamp":1259845947000},"page":"238-249","source":"Crossref","is-referenced-by-count":3,"title":["Hardness Results and Efficient Algorithms for Graph Powers"],"prefix":"10.1007","author":[{"given":"Van Bang","family":"Le","sequence":"first","affiliation":[]},{"given":"Ngoc Tuy","family":"Nguyen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","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.\u00a04059, pp. 411\u2013422. Springer, Heidelberg (2006)"},{"key":"21_CR2","first-page":"23","volume":"24 B","author":"E. Dahlhaus","year":"1987","unstructured":"Dahlhaus, E., Duchet, P.: On strongly chordal graphs. Ars Combin.\u00a024 B, 23\u201330 (1987)","journal-title":"Ars Combin."},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0012-365X(83)90154-1","volume":"43","author":"M. Farber","year":"1983","unstructured":"Farber, M.: Characterizations of strongly chordal graphs. Discrete Math.\u00a043, 173\u2013189 (1983)","journal-title":"Discrete Math."},{"key":"21_CR4","unstructured":"Farzad, B., Lau, L.C., Le, V.B., Nguyen, N.T.: Computing graph roots without short cycles. In: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pp. 397\u2013408 (2009)"},{"key":"21_CR5","volume-title":"Computers and Intractability\u2013A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability\u2013A Guide to the Theory of NP-Completeness. Freeman, New York (1979); Twenty-third printing (2002)"},{"key":"21_CR6","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"21_CR7","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A. Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Computing\u00a07, 413\u2013423 (1978)","journal-title":"SIAM J. Computing"},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1006\/jagm.1998.9999","volume":"29","author":"P.E. Kearney","year":"1998","unstructured":"Kearney, P.E., Corneil, D.G.: Tree powers. J. Algorithms\u00a029, 111\u2013131 (1998)","journal-title":"J. Algorithms"},{"key":"21_CR9","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1145\/1150334.1150337","volume":"2","author":"L.C. Lau","year":"2006","unstructured":"Lau, L.C.: Bipartite roots of graphs. ACM Transactions on Algorithms\u00a02, 178\u2013208 (2006); Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 952\u2013961","journal-title":"ACM Transactions on Algorithms"},{"key":"21_CR10","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1137\/S0895480103425930","volume":"18","author":"L.C. Lau","year":"2004","unstructured":"Lau, L.C., Corneil, D.G.: Recognizing powers of proper interval, split and chordal graphs. SIAM J. Discrete Math.\u00a018, 83\u2013102 (2004)","journal-title":"SIAM J. Discrete Math."},{"key":"21_CR11","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1137\/S089548019120016X","volume":"8","author":"Y.-L. Lin","year":"1995","unstructured":"Lin, Y.-L., Skiena, S.S.: Algorithms for square roots of graphs. SIAM J. Discrete Math.\u00a08, 99\u2013118 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"21_CR12","unstructured":"Lubiw, A.: \u0393-free matrices, Master Thesis, Dept. of Combinatorics and Optimization, University of Waterloo, Canada (1982)"},{"key":"21_CR13","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. Computing\u00a016, 854\u2013879 (1987)","journal-title":"SIAM J. Computing"},{"key":"21_CR14","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. Discrete Appl. Math.\u00a054, 81\u201388 (1994)","journal-title":"Discrete Appl. Math."},{"key":"21_CR15","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R. Paige","year":"1987","unstructured":"Paige, R., Tarjan, R.E.: Three partition refinement algorithms. SIAM J. Computing\u00a016, 973\u2013989 (1987)","journal-title":"SIAM J. Computing"},{"key":"21_CR16","first-page":"147","volume":"34","author":"A. Raychaudhuri","year":"1992","unstructured":"Raychaudhuri, A.: On powers of strongly chordal and circular arc graphs. Ars Combin.\u00a034, 147\u2013160 (1992)","journal-title":"Ars Combin."},{"key":"21_CR17","volume-title":"Efficient Graph Representations","author":"J.P. Spinrad","year":"2003","unstructured":"Spinrad, J.P.: Efficient Graph Representations. Fields Institute Monographs, Toronto (2003)"},{"key":"21_CR18","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. Computing\u00a06, 505\u2013517 (1977)","journal-title":"SIAM J. Computing"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11409-0_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T11:52:02Z","timestamp":1619783522000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11409-0_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642114083","9783642114090"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11409-0_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}