| 1. |
- 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)
|
|
| 2. |
- 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)
|
|
| 3. |
|
|
| 4. |
- 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)
|
|
| 5. |
- 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)
|
|
| 6. |
- 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.
|
|
| 7. |
- 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.
|
|
| 8. |
|
|
| 9. |
|
|
| 10. |
- Dell, Holger, et al.
(författare)
-
Exponential Time Complexity of the Permanent and the Tutte Polynomial
- 2010
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- The Exponential Time Hypothesis (ETH) says that deciding the satisfiability of n-variable 3-CNF formulas requires time exp((n)). We relax this hypothesis by introducing its counting version #ETH, namely that every algorithm that counts the satisfying assignments requires time exp((n)). We transfer the sparsification lemma for d-CNF formulas to the counting setting, which makes #ETH robust. Under this hypothesis, we show lower bounds for well-studied #P-hard problems: Computing the permanent of an nn matrix with m nonzero entries requires time exp((m)). Restricted to 01-matrices, the bound is exp((mlogm)) . Computing the Tutte polynomial of a multigraph with n vertices and m edges requires time exp((n)) at points (xy) with (x−1)(y−1)=1 and y01 . At points (x0) with x01 it requires time exp((n)), and if x=−2−3 , it requires time exp((m)). For simple graphs, the bound is exp((mlog3m)) .
|
|
