The Library
Faster exponential-time algorithms in graphs of bounded average degree
Tools
Tools
Tools
Cygan, Marek and Pilipczuk, Marcin (2015) Faster exponential-time algorithms in graphs of bounded average degree. Information and Computation, 243 . pp. 75-85. doi:10.1016/j.ic.2014.12.007 ISSN 0890-5401.
|
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, Engineering and Medicine > 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: | August 2015 | ||||||||
| Dates: |
|
||||||||
| Volume: | 243 | ||||||||
| Number of Pages: | 11 | ||||||||
| Page Range: | pp. 75-85 | ||||||||
| DOI: | 10.1016/j.ic.2014.12.007 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Date of first compliant deposit: | 28 December 2015 | ||||||||
| Date of first compliant Open Access: | 28 December 2015 | ||||||||
| 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
