Counting paths and packings in halves
(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:
https://lup.lub.lu.se/record/1628612
- author
- Björklund, Andreas LU ; Husfeldt, Thore LU ; Kaski, Petteri and Koivisto, Mikko
- organization
- publishing date
- 2009
- 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
- 2025-01-15 01:13:45
@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}}, }