The complexity of Boolean matrix root computation
type: Item
instance of: scholarly article
title: The complexity of Boolean matrix root computation
zbMATH Open document ID: 1071.68031
author: Martin Kuetz
published in: Theoretical Computer Science
publication date: 2004-10-27T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 20M99
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 2110948
zbMATH Keywords: Boolean matrix
zbMATH Keywords: Root
zbMATH Keywords: Directed graph
zbMATH Keywords: Graph power
zbMATH Keywords: Binary relation
zbMATH Keywords: Computational complexity
zbMATH Keywords: Graph isomorphism
zbMATH Keywords: Subdivision
MaRDI profile type: Publication
full work available at URL: j.tcs.2004.02.041
OpenAlex ID: W1507513857
cites work: The Transitive Reduction of a Directed Graph
cites work: Q4500916
cites work: Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
cites work: Q3619797
cites work: On the Sequence of Consecutive Powers of a Matrix in a Boolean Algebra
cites work: Q4198056
cites work: On the complexity of H-coloring
cites work: Newton's Method for the Matrix Square Root
cites work: Uniqueness of matrix square roots and an application
cites work: On the complexity of polytope isomorphism problems
cites work: Q3958592
cites work: Q4273947
cites work: A Padé Approximation Method for Square Roots of Symmetric Positive Definite Matrices
cites work: Some NP-Complete Problems Similar to Graph Isomorphism
cites work: Ordering \(D\)-classes and computing Schein rank is hard
cites work: A note on the graph isomorphism counting problem
cites work: Computing roots of graphs is hard
cites work: Efficient determination of the transitive closure of a directed graph
cites work: On the \(m\)-th roots of a complex matrix
cites work: Q4040446
DOI: 10.1016/J.TCS.2004.02.041
description: scientific article; zbMATH DE number 2110948