TY - GEN

T1 - Counting paths and packings in halves

AU - Björklund, Andreas

AU - Husfeldt, Thore

AU - Kaski, Petteri

AU - Koivisto, Mikko

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-04128-0_52

DO - 10.1007/978-3-642-04128-0_52

M3 - Paper in conference proceeding

VL - 5757

SP - 578

EP - 586

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

PB - Springer

T2 - 17th Annual European Symposium on Algorithms

Y2 - 7 September 2009 through 9 September 2009

ER -