Faster exponential-time algorithms in graphs of bounded average degree
DOI10.1016/J.IC.2014.12.007zbMATH Open1334.68095OpenAlexW2950262288MaRDI QIDQ2347799FDOQ2347799
Authors: Marek Cygan, Marcin Pilipczuk 
Publication date: 9 June 2015
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2014.12.007
Recommendations
- Faster exponential-time algorithms in graphs of bounded average degree
- Counting perfect matchings as fast as Ryser
- On the number of Hamilton cycles in bounded degree graphs
- Approximating the permanent of graphs with large factors
- Exact algorithms for exact satisfiability and number of perfect matchings
moderately-exponential algorithmsbounded average degreecounting perfect matchingsminimum weight Hamiltonian cycle
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- The traveling salesman problem in bounded degree graphs
- A Dynamic Programming Approach to Sequencing Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the possibility of faster \textsc{SAT} algorithms
- Counting perfect matchings as fast as Ryser
- On the complexity of \(k\)-SAT
- Set partitioning via inclusion-exclusion
- Dynamic Programming Treatment of the Travelling Salesman Problem
- Fourier meets M\"{o}bius: fast subset convolution
- Families with infants: a general approach to solve hard partition problems
- Title not available (Why is that?)
- Exact algorithms for exact satisfiability and number of perfect matchings
- Evaluation of permanents in rings and semirings
- Trimmed Moebius inversion and graphs of bounded degree
- A permanent algorithm with \(\text{exp}[\Omega(n^{1/3}/2\text{ln}n)]\) expected speedup for \(0-1\) matrices
- Computing sparse permanents faster
- Partitioning into sets of bounded cardinality
Cited In (8)
- Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
- Title not available (Why is that?)
- A better lower bound on average degree of online \(k\)-list-critical graphs
- Counting integral points in polytopes via numerical analysis of contour integration
- Counting perfect matchings as fast as Ryser
- Faster exponential-time algorithms in graphs of bounded average degree
- Computing the permanent modulo a prime power
- The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
This page was built for publication: Faster exponential-time algorithms in graphs of bounded average degree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2347799)
