The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Counting paths and packings in halves

På svenska

Author

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

Summary, in English

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.

Publishing year

2009

Language

English

Pages

578-586

Publication/Series

Algorithms - ESA 2009, Proceedings/Lecture notes in computer science

Volume

5757

Document type

Conference paper

Publisher

Springer

Topic

  • Computer Science

Conference name

17th Annual European Symposium on Algorithms

Conference date

2009-09-07 - 2009-09-09

Status

Published

Project

  • Exact algorithms

Research group

  • Algorithms

ISBN/ISSN/Other

  • ISSN: 0302-9743
  • ISSN: 1611-3349