The complexity of Boolean matrix root computation

DOI10.1016/J.TCS.2004.02.041MaRDI QIDQ1884841zbMATH OpenOpenAlexFDO

Authors 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

Boolean matrixComputational complexitySubdivisionRootDirected graphBinary relationGraph isomorphismGraph power

Mathematics Subject Classification ID

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

Recommendations

• The complexity of Boolean matrix root computation
• Boolean matrix root computing and the relations between square roots of Boolean matrices and chromatic partitions of graphs
• Some properties of square roots for a Boolean matrix
• On complexity of Boolean matrix polynomials solving
• Computing roots of graphs is hard

Cites work

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

Cited in

(9)

• Notes on logics of metric spaces
• The complexity of Boolean matrix root computation
• On complexity of Boolean matrix polynomials solving
• Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices
• Some properties of square roots for a Boolean matrix
• A constraint optimization approach to causal discovery from subsampled time series data
• Matrix roots in the max-plus algebra
• Combination of roots and Boolean operations: an application to state complexity
• Boolean matrix root computing and the relations between square roots of Boolean matrices and chromatic partitions of graphs

This page was built for publication: The complexity of Boolean matrix root computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1884841)