The complexity of Boolean matrix root computation

DOI10.1016/J.TCS.2004.02.041zbMATH Open1071.68031OpenAlexW1507513857MaRDI QIDQ1884841FDOQ1884841

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

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

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)

Cites Work

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

Cited In (9)

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

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)