{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:47:34Z","timestamp":1725493654580},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540405344"},{"type":"electronic","value":"9783540450719"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45071-8_23","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T08:04:43Z","timestamp":1193472283000},"page":"212-221","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Boolean Matrix Root Computation"],"prefix":"10.1007","author":[{"given":"Martin","family":"Kutz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,24]]},"reference":[{"issue":"2","key":"23_CR1","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1137\/0201008","volume":"1","author":"A. V. Aho","year":"1972","unstructured":"A. V. Aho, M. R. Garey, and J. D. Ullman. The transitive reduction of a directed graph. SIAM Journal on Computing, 1(2):131\u2013137, 1972.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"23_CR2","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1137\/0207023","volume":"7","author":"K. S. Booth","year":"1978","unstructured":"Kellogg S. Booth. Isomorphism testing for graphs, semigroups, and finite automata are polynomially equivalent problems. SIAM Journal on Computing, 7(3):273\u2013279, 1978.","journal-title":"SIAM Journal on Computing"},{"key":"23_CR3","unstructured":"Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms, chapter 26. MIT Press, 1990."},{"issue":"1","key":"23_CR4","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1137\/S0895479897326079","volume":"21","author":"B. Schutter de","year":"1999","unstructured":"Bart de Schutter and Bart de Moor. On the sequence of consecutive powers of a matrix in a Boolean algebra. SIAM Journal on Matrix Analysis and Applications, 21(1):328\u2013354, 1999.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"23_CR5","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"Pavol Hell and Jaroslav Ne\u0161et\u0159il. On the complexity of H-coloring. Journal of Combinatorial Theory, Series B, 48:92\u2013110, 1990.","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"174","key":"23_CR6","doi-asserted-by":"publisher","first-page":"537","DOI":"10.2307\/2007992","volume":"46","author":"N. J. Higham","year":"1986","unstructured":"Nicholas J. Higham. Newton\u2019s method for the matrix square root. Mathematics of Computation, 46(174):537\u2013549, 1986.","journal-title":"Mathematics of Computation"},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/S0024-3795(00)00243-3","volume":"323","author":"C. R. Johnson","year":"2001","unstructured":"C. R. Johnson, K. Okubo, and R. Reams. Uniqueness of matrix square roots and an application. Linear Algebra and Applications, 323:52\u201360, 2001.","journal-title":"Linear Algebra and Applications"},{"key":"23_CR8","unstructured":"Volker Kaibel and Alexander Schwartz. On the complexity of isomorphism problems related to polytopes. To appear in Graphs and Combinatorics."},{"key":"23_CR9","unstructured":"Ki Hang Kim. Boolean matrix theory and applications. Marcel Dekker, Inc., 1982."},{"key":"23_CR10","doi-asserted-by":"crossref","unstructured":"Johannes K\u00f6bler, Uwe Sch\u00f6ning, and Jacobo Tor\u00e1n. The graph isomorphism problem. Birkh\u00e4user, 1993.","DOI":"10.1007\/978-1-4612-0333-9"},{"issue":"3","key":"23_CR11","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1137\/S089547989731631X","volume":"19","author":"Y. Y. Lu","year":"1998","unstructured":"Ya Yan Lu. A Pad\u00e9 approximation method for square roots of symmetric positive definite matrices. SIAM Journal on Matrix Analysis and Applications, 19(3):833\u2013845, 1998.","journal-title":"SIAM Journal on Matrix Analysis and Applications"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"Anna Lubiw. Some NP-complete problems similar to graph isomorphism. SIAM Journal on Computing, 1981.","DOI":"10.1137\/0210002"},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/BF02574357","volume":"44","author":"G. Markowsky","year":"1992","unstructured":"George Markowsky. Ordering D-classes and computing Shein rank is hard. Semigroup Forum, 44:373\u2013375, 1992.","journal-title":"Semigroup Forum"},{"issue":"3","key":"23_CR14","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0020-0190(79)90004-8","volume":"8","author":"R. Mathon","year":"1979","unstructured":"Rudolph Mathon. A note on the graph isomorphism counting problem. Information Processing Letters, 8(3):131\u2013132, 1979.","journal-title":"Information Processing Letters"},{"issue":"1","key":"23_CR15","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0166-218X(94)00023-9","volume":"54","author":"R. Motwani","year":"1994","unstructured":"Rajeev Motwani and Madhu Sudan. Computing roots of graphs is hard. Discrete Applied Mathematics, 54(1):81\u201388, 1994.","journal-title":"Discrete Applied Mathematics"},{"key":"23_CR16","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/0020-0190(71)90006-8","volume":"1","author":"I. Munro","year":"1971","unstructured":"Ian Munro. Efficient determination of the transitive closure of a directed graph. Information Processing Letters, 1:56\u201358, 1971.","journal-title":"Information Processing Letters"},{"key":"23_CR17","doi-asserted-by":"crossref","first-page":"32","DOI":"10.13001\/1081-3810.1071","volume":"9","author":"P. J. Psarrakos","year":"2002","unstructured":"Panayiotis J. Psarrakos. On the mth roots of a complex matrix. The Electronic Journal of Linear Algebra, 9:32\u201341, 2002.","journal-title":"The Electronic Journal of Linear Algebra"},{"key":"23_CR18","unstructured":"Kenneth A. Ross and Charles R. B. Wright. Discrete mathematics, chapter 7.5. Prentice-Hall, second edition, 1988."},{"key":"23_CR19","unstructured":"Larry L. Stockmeyer. The minimal set basis problem is NP-complete. IBM Research Report No. RC-5431, IBM Thomas J. Watson Research Center, 1975."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45071-8_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T02:09:11Z","timestamp":1556935751000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45071-8_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405344","9783540450719"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-45071-8_23","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}