Bounded Treewidth and Space-Efficient Linear Algebra

DOI10.1007/978-3-319-17142-5_26zbMath1460.68043arXiv1412.2470OpenAlexW1908819570MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

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

This page was built for publication: Bounded Treewidth and Space-Efficient Linear Algebra