Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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 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
; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Algorithms - ESA 2009, Proceedings/Lecture notes in computer science
volume
5757
pages
578 - 586
publisher
Springer
conference name
17th Annual European Symposium on Algorithms
conference dates
2009-09-07 - 2009-09-09
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
2016-04-01 11:57:56
date last changed
2024-03-11 12:20:44
@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}},
  doi          = {{10.1007/978-3-642-04128-0_52}},
  volume       = {{5757}},
  year         = {{2009}},
}