scientific article; zbMATH DE number 7053325
From MaRDI portal
Publication:5743447
zbMath1422.68103arXiv1107.4466MaRDI QIDQ5743447
Publication date: 10 May 2019
Full work available at URL: https://arxiv.org/abs/1107.4466
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
What Circuit Classes Can Be Learned with Non-Trivial Savings?, Space saving by dynamic algebraization based on tree-depth, Counting Integral Points in Polytopes via Numerical Analysis of Contour Integration, Counting near-perfect matchings on \(C_m \times C_n\) tori of odd order in the Maple system, Fine-grained dichotomies for the Tutte plane and Boolean \#CSP, Shortest \((A+B)\)-path packing via hafnian, Counting the number of perfect matchings, and generalized decision trees, The combinatorics of N. G. de Bruijn, Faster exponential-time algorithms in graphs of bounded average degree, Constrained multilinear detection and generalized graph motifs
Cites Work
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Exact algorithms for exact satisfiability and number of perfect matchings
- Computing sparse permanents faster
- Dynamic programming meets the principle of inclusion and exclusion
- Which problems have strongly exponential complexity?
- Saving space by algebraization
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Fourier meets M\"{o}bius: fast subset convolution
- Set Partitioning via Inclusion-Exclusion
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
- Partitioning into Sets of Bounded Cardinality
- Counting Subgraphs via Homomorphisms
- A permanent algorithm with \(\text{exp}[\Omega(n^{1/3}/2\text{ln}n)\) expected speedup for \(0-1\) matrices]
