Determinant: Old Algorithms, New Insights

DOI10.1137/S0895480198338827zbMath0971.05072OpenAlexW2027897659MaRDI QIDQ4699172

V. Vinay, Meena Mahajan

Publication date: 23 November 1999

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480198338827

zbMATH Keywords

combinatoricsalgorithmscharacteristic polynomialmatricesgraphsdeterminantmatrixclosed walks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Determinants, permanents, traces, other special matrix functions (15A15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

On the linear classification of even and odd permutation matrices and the complexity of computing the permanent, Faster combinatorial algorithms for determinant and Pfaffian, The complexity of the characteristic and the minimal polynomial., Unnamed Item, A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem., On the exact evaluation of spin networks, The quantum query complexity of the determinant, Counting the number of perfect matchings, and generalized decision trees, Factorization of polynomials given by arithmetic branching programs, Factorization of polynomials given by arithmetic branching programs, Functional programming concepts and straight-line programs in computer algebra, Noncommutativity makes determinants hard