Bounded Treewidth and Space-Efficient Linear Algebra

DOI10.1007/978-3-319-17142-5_26zbMath1460.68043arXiv1412.2470MaRDI QIDQ2948475

Nikhil Balaji, Samir Datta

Publication date: 30 September 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.2470

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C30: Enumeration in graph theory

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

An efficient tree decomposition method for permanents and mixed discriminants

Cites Work

• Unnamed Item
• Log-space algorithms for paths and matchings in \(k\)-trees
• Exact counting of Euler tours for generalized series-parallel graphs
• On computing the determinant in small parallel time using a small number of processors
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• Counting quantifiers, successor relations, and logarithmic space
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• The complexity of matrix rank and feasible systems of linear equations
• Parametrized complexity theory.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Modern Computer Algebra
• On the Ordered Conjecture
• Algebraic Combinatorics
• On Unicursal Paths in a Network of Degree 4
• Planarity, Determinants, Permanents, and (Unique) Matchings