Tyck till om SwePub Sök
här!
Sökning: onr:"swepub:oai:lup.lub.lu.se:30f89e87-7803-4da5-b197-f8a0caa3c99f" >
Counting paths and ...
Counting paths and packings in halves
-
- Björklund, Andreas (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
- Husfeldt, Thore (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
Kaski, Petteri (författare)
-
visa fler...
-
Koivisto, Mikko (författare)
-
visa färre...
-
(creator_code:org_t)
- Berlin, Heidelberg : Springer Berlin Heidelberg, 2009
- 2009
- Engelska.
-
Ingår i: Algorithms - ESA 2009, Proceedings/Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. ; 5757, s. 578-586
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
http://arxiv.org/pdf...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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)
Hitta via bibliotek
Till lärosätets databas