Sökning: id:"swepub:oai:lup.lub.lu.se:3940d76c-c6d0-41d8-9401-50b95fdc1c1d" >
Fast Witness Extrac...
Fast Witness Extraction using a Decision Oracle
-
- 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
-
Kaski, Petteri (författare)
-
Kowalik, Lukasz (författare)
-
visa fler...
-
Schulz, Andreas (redaktör/utgivare)
-
Wagner, Dorothea (redaktör/utgivare)
-
visa färre...
-
(creator_code:org_t)
- Berlin, Heidelberg : Springer Berlin Heidelberg, 2014
- 2014
- Engelska 12 s.
-
Ingår i: Algorithms - ESA 2014/Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783662447772 ; 8737, s. 149-160
- 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
- The gist of many (NP-)hard combinatorial problems is to decide whether a universe of n elements contains a witness consisting of k elements that match some prescribed pattern. For some of these problems there are known advanced algebra-based FPT algorithms which solve the decision problem but do not return the witness. We investigate techniques for turning such a YES/NO-decision oracle into an algorithm for extracting a single witness, with an objective to obtain practical scalability for large values of n. By relying on techniques from combinatorial group testing, we demonstrate that a witness may be extracted with O(klogn) queries to either a deterministic or a randomized set inclusion oracle with one-sided probability of error. Furthermore, we demonstrate through implementation and experiments that the algebra-based FPT algorithms are practical, in particular in the setting of the k-path problem. Also discussed are engineering issues such as optimizing finite field arithmetic.
Ä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