The Library
Faster exponential-time algorithms in graphs of bounded average degree
Tools
Tools
Tools
Cygan, Marek and Pilipczuk, Marcin (2013) Faster exponential-time algorithms in graphs of bounded average degree. Information and Computation . doi:10.1016/j.ic.2014.12.007 (In Press)
|
PDF
WRAP_1371795-cs-270115-ave-degree.pdf - Accepted Version - Requires a PDF viewer. Download (353Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.ic.2014.12.007
Abstract
We present a number of exponential-time algorithms for problems in sparse matrices and graphs of bounded average degree. First, we obtain a simple algorithm that computes a permanent of an n×n matrix over an arbitrary commutative ring with at most dn non-zero entries using O⋆(2(1−1/(3.55d))n) time and ring operations, 1 improving and simplifying the recent result of Izumi and Wadayama [FOCS 2012].
Second, we present a simple algorithm for counting perfect matchings in an n -vertex graph in O⋆(2n/2) time and polynomial space; our algorithm matches the complexity bounds of the algorithm of Björklund [SODA 2012], but relies on inclusion–exclusion principle instead of algebraic transformations.
Third, we show a combinatorial lemma that bounds the number of “Hamiltonian-like” structures in a graph of bounded average degree. Using this result, we show that
1. a minimum weight Hamiltonian cycle in an n-vertex graph with average degree bounded by d can be found in O⋆(2(1−εd)n) time and exponential space for a constant εd depending only on d;
2. the number of perfect matchings in an n-vertex graph with average degree bounded by d can be computed in View the MathML source time and exponential space, for a constant View the MathML source depending only on d.
The algorithm for minimum weight Hamiltonian cycle generalizes the recent results of Björklund et al. [TALG 2012] on graphs of bounded degree.
| Item Type: | Journal Article | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
| Divisions: | Faculty of Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Computer algorithms, Hamiltonian systems | ||||||
| Journal or Publication Title: | Information and Computation | ||||||
| Publisher: | Academic Press | ||||||
| ISSN: | 0890-5401 | ||||||
| Official Date: | 15 August 2013 | ||||||
| Dates: |
|
||||||
| Date of first compliant deposit: | 28 December 2015 | ||||||
| Number of Pages: | 11 | ||||||
| DOI: | 10.1016/j.ic.2014.12.007 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | In Press | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Funder: | Narodowe Centrum Nauki (NCN), Fundacja na rzecz Nauki Polskiej [Foundation for Polish Science] (FNP) | ||||||
| Grant number: | N206567140 (NCN) |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
