1. |
- Björklund, Andreas, et al.
(författare)
-
Shortest Two Disjoint Paths in Polynomial Time
- 2014
-
Ingår i: Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783662439470 ; 8572, s. 211-222
-
Konferensbidrag (refereegranskat)abstract
- Given an undirected graph and two pairs of vertices $(s_i,t_i)$ for $i\in\{1,2\}$ we show that there is a polynomial time Monte Carlo algorithm that finds disjoint paths of smallest total length joining $s_i$ and $t_i$ for $i\in\{1,2\}$ respectively, or concludes that there most likely are no such paths at all. Our algorithm applies to both the vertex- and edge-disjoint versions of the problem. Our algorithm is algebraic and uses permanents over the polynomial rings $Z_2[x]$ and $Z_4[x]$ in combination with Mulmuley, Vazirani and Vazirani's isolation lemma to detect a solution. We develop a fast algorithm for permanents over these rings by modifying Valiant's 1979 algorithm for the permanent over $Z_{2^l}$.
|
|
2. |
|
|
3. |
- Björklund, Andreas, et al.
(författare)
-
Covering and packing in linear space
- 2011
-
Ingår i: Information Processing Letters. - : Elsevier BV. - 0020-0190. ; 111:21–22, s. 1033-1036
-
Tidskriftsartikel (refereegranskat)
|
|
4. |
- Björklund, Andreas, et al.
(författare)
-
Covering and packing in linear space
- 2010
-
Ingår i: Automata, Languages and Programming /Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. ; 6198, s. 727-737
-
Konferensbidrag (refereegranskat)
|
|
5. |
|
|
6. |
- Björklund, Andreas, et al.
(författare)
-
Fast zeta transforms for point lattices
- 2012
-
Ingår i: SODA '12 Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms. - Philadelphia, PA : Society for Industrial and Applied Mathematics. - 9781611972108 ; , s. 1436-1444
-
Konferensbidrag (refereegranskat)
|
|
7. |
- Björklund, Andreas, et al.
(författare)
-
Listing Triangles
- 2014
-
Ingår i: Automata, Languages, and Programming (Lecture notes in computer science). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783662439487 ; 8572, s. 223-234
-
Konferensbidrag (refereegranskat)abstract
- We present new algorithms for listing triangles in dense and sparse graphs. The running time of our algorithm for dense graphs is O~(n^ω+n^3(ω−1)/(5−ω)t^2(3−ω)/(5−ω)), and the running time of the algorithm for sparse graphs is O~(m^2ω/(ω+1)+m^3(ω−1)/(ω+1)t^(3−ω)/(ω+1)), where n is the number of vertices, m is the number of edges, t is the number of triangles to be listed, and ω < 2.373 is the exponent of fast matrix multiplication. With the current bound on ω, the running times of our algorithms are O~(n^2.373+n^1.568t^0.478) and O~(m^1.408+m^1.222t^0.186), respectively. We first obtain randomized algorithms with the desired running times and then derandomize them using sparse recovery techniques. If ω = 2, the running times of the algorithms become O~(n^2+nt^2/3) and O~(m^4/3+mt^1/3), respectively. In particular, if ω = 2, our algorithm lists m triangles in O~(m4/3) time. Pǎtraşcu (STOC 2010) showed that Ω(m^(4/3 − o(1))) time is required for listing m triangles, unless there exist subquadratic algorithms for 3SUM. We show that unless one can solve quadratic equation systems over a finite field significantly faster than the brute force algorithm, our triangle listing runtime bounds are tight assuming ω = 2, also for graphs with more triangles.
|
|
8. |
- Björklund, Andreas, et al.
(författare)
-
Shortest cycle through specified elements
- 2012
-
Ingår i: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms. ; , s. 1747-1747
-
Konferensbidrag (refereegranskat)
|
|
9. |
- Björklund, Andreas, et al.
(författare)
-
The Parity of Directed Hamiltonian Cycles
- 2013
-
Ingår i: Annual IEEE Symposium on Foundations of Computer Science. - 0272-5428. ; , s. 727-735
-
Konferensbidrag (refereegranskat)abstract
- We present a deterministic algorithm that given any directed graph on n vertices computes the parity of its number of Hamiltonian cycles in O(1.619n) time and polynomial space. For bipartite graphs, we give a 1.5npoly(n) expected time algorithm. Our algorithms are based on a new combinatorial formula for the number of Hamiltonian cycles modulo a positive integer.
|
|
10. |
- Björklund, Andreas, et al.
(författare)
-
The Traveling Salesman Problem in Bounded Degree Graphs
- 2012
-
Ingår i: ACM Transactions on Algorithms. - : Association for Computing Machinery (ACM). - 1549-6333 .- 1549-6325. ; 8:2, s. 18-18
-
Tidskriftsartikel (refereegranskat)abstract
- We show that the traveling salesman problem in bounded-degree graphs can be solved in time O((2 - epsilon)(n)), where epsilon > 0 depends only on the degree bound but not on the number of cities, n. The algorithm is a variant of the classical dynamic programming solution due to Bellman, and, independently, Held and Karp. In the case of bounded integer weights on the edges, we also give a polynomial-space algorithm with running time O(( 2 - epsilon)(n)) on bounded-degree graphs. In addition, we present an analogous analysis of Ryser's algorithm for the permanent of matrices with a bounded number of nonzero entries in each column.
|
|