Counting paths and packings in halves

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingpeer-review

40 Citations (SciVal)

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.
Original languageEnglish
Title of host publicationAlgorithms - ESA 2009, Proceedings/Lecture notes in computer science
PublisherSpringer
Pages578-586
Volume5757
DOIs
Publication statusPublished - 2009
Event17th Annual European Symposium on Algorithms - Copenhagen, DENMARK
Duration: 2009 Sep 72009 Sep 9

Publication series

Name
Volume5757
ISSN (Print)1611-3349
ISSN (Electronic)0302-9743

Conference

Conference17th Annual European Symposium on Algorithms
Period2009/09/072009/09/09

Subject classification (UKÄ)

  • Computer Science

Fingerprint

Dive into the research topics of 'Counting paths and packings in halves'. Together they form a unique fingerprint.

Cite this