Sökning: id:"swepub:oai:lup.lub.lu.se:33da8859-e245-43c4-a8c5-b8bb2fe61b13" >
Approximate Countin...
Approximate Counting of k-Paths : Simpler, Deterministic, and in Polynomial Space
-
- Lokshtanov, Daniel (författare)
- University of California, Santa Barbara,The Institute of Mathematical Sciences
-
- 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
-
- Saurabh, Saket (författare)
- Ben Gurion University of the Negev
-
visa fler...
-
- Zehavi, Meirav (författare)
- Ben Gurion University of the Negev
-
visa färre...
-
(creator_code:org_t)
- 2021-07-15
- 2021
- Engelska.
-
Ingår i: ACM Transactions on Algorithms. - : Association for Computing Machinery (ACM). - 1549-6325 .- 1549-6333. ; 17:3
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Recently, Brand et al. [STOC 2018] gave a randomized mathcal O(4kmϵ-2-time exponential-space algorithm to approximately compute the number of paths on k vertices in a graph G up to a multiplicative error of 1 ± ϵ based on exterior algebra. Prior to our work, this has been the state-of-the-art. In this article, we revisit the algorithm by Alon and Gutner [IWPEC 2009, TALG 2010], and obtain the following results: •We present a deterministic 4k+ O(sk(log k+log2ϵ-1))m-time polynomial-space algorithm. This matches the running time of the best known deterministic polynomial-space algorithm for deciding whether a given graph G has a path on k vertices. •Additionally, we present a randomized 4k+mathcal O(logk(logk+logϵ-1))m-time polynomial-space algorithm. Our algorithm is simple - we only make elementary use of the probabilistic method. Here, n and m are the number of vertices and the number of edges, respectively. Additionally, our approach extends to approximate counting of other patterns of small size (such as q-dimensional p-matchings).
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- k-path
- Parameterized complexity
- parameterized counting problems
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas