Counting paths and packings in halves

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

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Publikations- och innehållstyp

kon (ämneskategori)

ref (ämneskategori)