Sökning: onr:"swepub:oai:lup.lub.lu.se:a7926a8a-cf52-4d7d-a293-1a65282a302e" >
Narrow sieves for p...
Narrow sieves for parameterized paths and packings
-
- 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,IT University of Copenhagen
-
- Kaski, Petteri (författare)
- Aalto University
-
visa fler...
-
- Koivisto, Mikko (författare)
- University of Helsinki
-
visa färre...
-
(creator_code:org_t)
- Elsevier BV, 2017
- 2017
- Engelska.
-
Ingår i: Journal of Computer and System Sciences. - : Elsevier BV. - 0022-0000. ; 87, s. 119-139
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://doi.org/10.1...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- We present parameterized algorithms for the k-path problem, the p-packing of q-sets problem, and the q-dimensional p-matching problem. Our algorithms solve these problems with high probability in time exponential only in the parameter (k, p, q) and using polynomial space. The constant bases of the exponentials are significantly smaller than in previous works; for example, for the k-path problem the improvement is from 2 to 1.66. We also show how to detect if a d-regular graph admits an edge coloring with d colors in time within a polynomial factor of 2(d-1)n/2. Our techniques generalize an algebraic approach studied in various recent works.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Determinant
- Edge coloring
- Graph algorithm
- k-Path
- Multidimensional matching
- Polynomial identity testing
- Randomized algorithm
- Set packing
- Sieve
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas