Faster exponential-time algorithms in graphs of bounded average degree

DOI10.1016/J.IC.2014.12.007MaRDI QIDQ2347799zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

moderately-exponential algorithmsbounded average degreecounting perfect matchingsminimum weight Hamiltonian cycle

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 3182201 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 6783432 (Why is no real title available?)
• A Dynamic Programming Approach to Sequencing Problems
• A permanent algorithm with \(\text{exp}[\Omega(n^{1/3}/2\text{ln}n)]\) expected speedup for \(0-1\) matrices
• Computing sparse permanents faster
• Counting perfect matchings as fast as Ryser
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Evaluation of permanents in rings and semirings
• Exact algorithms for exact satisfiability and number of perfect matchings
• Families with infants: a general approach to solve hard partition problems
• Fourier meets M\"{o}bius: fast subset convolution
• On the complexity of \(k\)-SAT
• On the possibility of faster \textsc{SAT} algorithms
• Partitioning into sets of bounded cardinality
• Set partitioning via inclusion-exclusion
• The traveling salesman problem in bounded degree graphs
• Trimmed Moebius inversion and graphs of bounded degree

Cited in

(8)

• Computing the permanent modulo a prime power
• Counting perfect matchings as fast as Ryser
• The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
• Exploiting sparsity for bipartite Hamiltonicity
• Counting integral points in polytopes via numerical analysis of contour integration
• Faster exponential-time algorithms in graphs of bounded average degree
• A better lower bound on average degree of online \(k\)-list-critical graphs
• Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors

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)