Advanced

Counting paths and packings in halves

Björklund, Andreas LU ; Husfeldt, Thore LU ; Kaski, Petteri and Koivisto, Mikko (2009) 17th Annual European Symposium on Algorithms In Algorithms - ESA 2009, Proceedings/Lecture notes in computer science 5757. p.578-586
Abstract
We show that; one can count k-edge paths in an n-vertex graph and m-set k-packings on an n-element universe, respectively, in time (n k/2) and (n mk/2) up to a factor polynomial in n, k, and in: in polynomial space, the bounds hold if multiplied by 3(k/2) or 5(mk/2), respectively. These are implications of a more general result: given two set families on an n-element universe, one can count the disjoint pairs of sets in the Cartesian product of the two families with O(The) basic operations, where e is the number of members in the two families and their subsets.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Algorithms - ESA 2009, Proceedings/Lecture notes in computer science
volume
5757
pages
578 - 586
publisher
Springer
conference name
17th Annual European Symposium on Algorithms
external identifiers
  • wos:000279102100052
  • scopus:70350761404
ISSN
0302-9743
1611-3349
DOI
10.1007/978-3-642-04128-0_52
project
Exact algorithms
language
English
LU publication?
yes
id
30f89e87-7803-4da5-b197-f8a0caa3c99f (old id 1628612)
date added to LUP
2010-07-23 09:50:24
date last changed
2017-10-22 03:42:19
@inproceedings{30f89e87-7803-4da5-b197-f8a0caa3c99f,
  abstract     = {We show that; one can count k-edge paths in an n-vertex graph and m-set k-packings on an n-element universe, respectively, in time (n k/2) and (n mk/2) up to a factor polynomial in n, k, and in: in polynomial space, the bounds hold if multiplied by 3(k/2) or 5(mk/2), respectively. These are implications of a more general result: given two set families on an n-element universe, one can count the disjoint pairs of sets in the Cartesian product of the two families with O(The) basic operations, where e is the number of members in the two families and their subsets.},
  author       = {Björklund, Andreas and Husfeldt, Thore and Kaski, Petteri and Koivisto, Mikko},
  booktitle    = {Algorithms - ESA 2009, Proceedings/Lecture notes in computer science},
  issn         = {0302-9743},
  language     = {eng},
  pages        = {578--586},
  publisher    = {Springer},
  title        = {Counting paths and packings in halves},
  url          = {http://dx.doi.org/10.1007/978-3-642-04128-0_52},
  volume       = {5757},
  year         = {2009},
}