Counting paths and packings in halves

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.

• Författare: Andreas Björklund; Thore Husfeldt; Petteri Kaski; Mikko Koivisto
• Avdelning/ar: Institutionen för datavetenskap; Parallella System
• Publiceringsår: 2009
• Språk: Engelska
• Sidor: 578-586
• Publikation/Tidskrift/Serie: Algorithms - ESA 2009, Proceedings/Lecture notes in computer science
• Volym: 5757
• Länkar: http://dx.doi.org/10.1007/978-3-642-04128-0_52
• Dokumenttyp: Konferensbidrag
• Förlag: Springer
• Ämne: Computer Science
• Conference name: 17th Annual European Symposium on Algorithms
• Conference date: 2009-09-07 - 2009-09-09
• Status: Published
• Projekt: Exact algorithms
• Forskningsgrupp: Algorithms
• ISBN/ISSN/Övrigt: ISSN: 0302-9743; ISSN: 1611-3349