| 1. |
- Alstrup, Stephen, et al.
(författare)
-
Black box for constant-time insertion in priority queues
- 2005
-
Ingår i: ACM Transactions on Algorithms. - : Association for Computing Machinery (ACM). - 1549-6333 .- 1549-6325. ; 1:1, s. 102-106
-
Tidskriftsartikel (refereegranskat)abstract
- We present a simple black box that takes a priority queue Q which supports find-min, insert, and delete in x-time at most t. Here x-time may be worst-case, expected, or amortized. The black-box transforms Q into a priority queue Q* that supports find-min in constant time, insert in constant x-time, and delete in x-time O(t). Moreover, if Q supports dec-key in constant time, then so does Q*.
|
|
| 2. |
- Björklund, Andreas, et al.
(författare)
-
Computing the Tutte polynomial in vertex-exponential time
- 2008
-
Ingår i: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science. - 0272-5428. ; , s. 677-686
-
Konferensbidrag (refereegranskat)abstract
- The deletion-contraction algorithm is perhaps the most popular method for computing a host of fundamental graph invariants such as the chromatic, flow, and reliability polynomials in graph theory, the Jones polynomial of an alternating link in knot theory, and the partition functions of the models of Ising, Potts, and Fortuin-Kasteleyn in statistical physics. Prior to this work, deletion-contraction was also the fastest known general-purpose algorithm for these invariants, running in time roughly proportional to the number of spanning trees in the input graph. Here, we give a substantially faster algorithm that computes the Tutte polynomial-and hence, all the aforementioned invariants and more-of an arbitrary graph in time within a polynomial factor of the number of connected vertex sets. The algorithm actually evaluates a multivariate generalization of the Tutte polynomial by making use of an identity due to Fortuin and Kasteleyn. We also provide a polynomial-space variant of the algorithm and give an analogous result for Chung and Graham's cover polynomial.
|
|
| 3. |
- Björklund, Andreas, et al.
(författare)
-
Counting paths and packings in halves
- 2009
-
Ingår i: Algorithms - ESA 2009, Proceedings/Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. ; 5757, s. 578-586
-
Konferensbidrag (refereegranskat)abstract
- We show that; one can count k-edge paths in an n-vertex graph and m-set k-packings on an n-element universe, respectively, in time (n k/2) and (n mk/2) up to a factor polynomial in n, k, and in: in polynomial space, the bounds hold if multiplied by 3(k/2) or 5(mk/2), respectively. These are implications of a more general result: given two set families on an n-element universe, one can count the disjoint pairs of sets in the Cartesian product of the two families with O(The) basic operations, where e is the number of members in the two families and their subsets.
|
|
| 4. |
- Björklund, Andreas, et al.
(författare)
-
Exact algorithms for exact satisfiability and number of perfect matchings
- 2006
-
Ingår i: Lecture Notes in Computer Science (Automata, Languages and Programming. Proceedings, Part I). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 9783540359043 ; 4051, s. 548-559
-
Konferensbidrag (refereegranskat)abstract
- We present exact algorithms with exponential running times for variants of n-element set cover problems, based on divide-and-conquer and on inclusion-exclusion characterisations. We show that the Exact Satisfiability problem of size 1 with m clauses can be solved in time 2(m)l(O(1)) and polynomial space. The same bounds hold for counting the number of solutions. As a special case, we can count the number of perfect matchings in an n-vertex graph in time 2(n)n(O(1)) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732(n)) and exponential space. Using the same techniques we show how to compute Chromatic Number of an n-vertex graph in time O(2.4423(n)) and polynomial space, or time O(2.3236(n)) and exponential space.
|
|
| 5. |
- Björklund, Andreas, et al.
(författare)
-
Exact algorithms for exact satisfiability and number of perfect matchings
- 2008
-
Ingår i: Algorithmica. - : Springer Science and Business Media LLC. - 0178-4617 .- 1432-0541. ; 52:2, s. 226-249
-
Tidskriftsartikel (refereegranskat)abstract
- We present exact algorithms with exponential running times for variants of n-element set cover problems, based on divide-and-conquer and on inclusion exclusion characterizations. We show that the Exact Satisfiability problem of size l with m clauses can be solved in time 2(m)l(O(1)) and polynomial space. The same bounds hold for counting the number of solutions. As a special case, we can count the number of perfect matchings in an n-vertex graph in time 2(n)n(O(1)) and polynomial space. We also show how to count the number of perfect matchings in time O(1.732(n)) and exponential space. We give a number of examples where the running time can be further improved if the hypergraph corresponding to the set cover instance has low pathwidth. This yields exponential-time algorithms for counting k-dimensional matchings, Exact Uniform Set Cover, Clique Partition, and Minimum Dominating Set in graphs of degree at most three. We extend the analysis to a number of related problems such as TSP and Chromatic Number.
|
|
| 6. |
- Björklund, Andreas, et al.
(författare)
-
Exact graph coloring using inclusion–exclusion
- 2008
-
Ingår i: Encyclopedia of Algorithms. - Boston, MA : Springer US. - 9780387301624 ; , s. 289-290
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)
|
|
| 7. |
- Björklund, Andreas, et al.
(författare)
-
Fourier meets Möbius: fast subset convolution
- 2007
-
Ingår i: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. - New York, NY, USA : ACM. - 9781595936318 ; , s. 67-74
-
Konferensbidrag (refereegranskat)abstract
- We present a fast algorithm for the subset convolution problem:given functions f and g defined on the lattice of subsets of ann-element set n, compute their subset convolution f*g, defined for S⊆ N by [ (f * g)(S) = [T ⊆ S] f(T) g(S/T),,]where addition and multiplication is carried out in an arbitrary ring. Via Möbius transform and inversion, our algorithm evaluates the subset convolution in O(n2 2n) additions and multiplications, substanti y improving upon the straightforward O(3n) algorithm. Specifically, if the input functions have aninteger range [-M,-M+1,...,M], their subset convolution over the ordinary sum--product ring can be computed in Õ(2n log M) time; the notation Õ suppresses polylogarithmic factors.Furthermore, using a standard embedding technique we can compute the subset convolution over the max--sum or min--sum semiring in Õ(2n M) time. To demonstrate the applicability of fast subset convolution, wepresent the first Õ(2k n2 + n m) algorithm for the Steiner tree problem in graphs with n vertices, k terminals, and m edges with bounded integer weights, improving upon the Õ(3kn + 2k n2 + n m) time bound of the classical Dreyfus-Wagner algorithm. We also discuss extensions to recent Õ(2n)-time algorithms for covering and partitioning problems (Björklund and Husfeldt, FOCS 2006; Koivisto, FOCS 2006).
|
|
| 8. |
- Björklund, Andreas, et al.
(författare)
-
Inclusion-exclusion algorithms for counting set partitions
- 2006
-
Ingår i: 2006 47th Annual IEEE Conference on Foundations of Computer Science. - 0769527205 ; , s. 575-582
-
Konferensbidrag (refereegranskat)abstract
- Given a set U with n elements and a family of subsets S ⊆ 2U we show how to count the number of k-partitions S1 ∪ ... ∪ Sk = U into subsets Si ∈ S in time 2nnO(1). The only assumption on S is that it can be enumerated in time 2nnO(1). In effect we get exact algorithms in time 2nnO(1) for several well-studied partition problems including domatic number, chromatic number, bounded component spanning forest, partition into Hamiltonian subgraphs, and bin packing. If only polynomial space is available, our algorithms run in time 3nnO(1) if membership in S can be decided in polynomial time. For chromatic number, we present a version that runs in time O(2.2461n) and polynomial space. For domatic number, we present a version that runs in time O(2.8718n). Finally, we present a family of polynomial space approximation algorithms that find a number between χ(G) and [(1 + ϵ)χ(G)] in time O(1.2209n + 2.2461e-ϵn)
|
|
| 9. |
- Björklund, Andreas, et al.
(författare)
-
Set partitioning via inclusion-exclusion
- 2009
-
Ingår i: SIAM Journal on Computing. - : Society for Industrial & Applied Mathematics (SIAM). - 0097-5397 .- 1095-7111. ; 39:2, s. 546-563
-
Tidskriftsartikel (refereegranskat)abstract
- Given a set N with n elements and a family F of subsets, we show how to partition N into k such subsets in 2(n) n(O)(1) time. We also consider variations of this problem where the subsets may overlap or are weighted, and we solve the decision, counting, summation, and optimization versions of these problems. Our algorithms are based on the principle of inclusion-exclusion and the zeta transform. In effect we get exact algorithms in 2(n) n(O)(1) time for several well-studied partition problems including domatic number, chromatic number, maximum k-cut, bin packing, list coloring, and the chromatic polynomial. We also have applications to Bayesian learning with decision graphs and to model-based data clustering. If only polynomial space is available, our algorithms run in time 3(n) n(O)(1) if membership in F can be decided in polynomial time. We solve chromatic number in O(2.2461(n)) time and domatic number in O(2.8718(n)) time. Finally, we present a family of polynomial space approximation algorithms that find a number between chi(G) and inverted right perpendicular(1 + epsilon)chi(G)inverted left perpendicular in time O(1.2209(n) + 2.2461(e-epsilon n)).
|
|
| 10. |
- Björklund, Andreas, et al.
(författare)
-
The travelling salesman problem in bounded degree graphs
- 2008
-
Ingår i: Automata, Languages and Programming, part 1, Proceedings/Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 9783540705741 ; 5125, s. 198-209
-
Konferensbidrag (refereegranskat)abstract
- We show that the travelling salesman problem in bounded-degree graphs can be solved in tune 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 present a polynomial-space algorithm with running tune O((2 - epsilon)(n)) on bounded-degree graphs.
|
|
