Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

Counting paths and packings in halves

Publiceringsår: 2009
Språk: Engelska
Sidor: 578-586
Publikation/Tidskrift/Serie: Algorithms - ESA 2009, Proceedings/Lecture notes in computer science
Volym: 5757
Dokumenttyp: Konferensbidrag
Förlag: Springer


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.


  • Computer Science


17th Annual European Symposium on Algorithms
  • Exact algorithms
  • Algorithms-lup-obsolete
  • ISSN: 1611-3349
  • ISSN: 0302-9743

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen