The complexity of Boolean matrix root computation

DOI10.1016/j.tcs.2004.02.041zbMath1071.68031OpenAlexW1507513857MaRDI QIDQ1884841

Martin Kuetz

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.02.041

zbMATH Keywords

Computational complexityBoolean matrixSubdivisionRootDirected graphBinary relationGraph isomorphismGraph power

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Semigroups (20M99)

Related Items

Notes on logics of metric spaces, A constraint optimization approach to causal discovery from subsampled time series data, Matrix roots in the max-plus algebra

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of H-coloring
• Ordering \(D\)-classes and computing Schein rank is hard
• A note on the graph isomorphism counting problem
• Computing roots of graphs is hard
• On the complexity of polytope isomorphism problems
• Efficient determination of the transitive closure of a directed graph
• On the m-th roots of a complex matrix
• Some NP-Complete Problems Similar to Graph Isomorphism
• Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
• A Padé Approximation Method for Square Roots of Symmetric Positive Definite Matrices
• On the Sequence of Consecutive Powers of a Matrix in a Boolean Algebra
• Newton's Method for the Matrix Square Root
• The Transitive Reduction of a Directed Graph
• Uniqueness of matrix square roots and an application