SwePub
Sök i SwePub databas

  Utökad sökning

Träfflista för sökning "WFRF:(Husfeldt Thore) "

Sökning: WFRF:(Husfeldt Thore)

  • Resultat 1-10 av 50
Sortera/gruppera träfflistan
   
NumreringReferensOmslagsbildHitta
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. - 0302-9743 .- 1611-3349. - 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.
  • 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*.
  •  
3.
  • Alstrup, S, et al. (författare)
  • Dynamic nested brackets
  • 2004
  • Ingår i: Information and Computation. - : Elsevier BV. - 1090-2651 .- 0890-5401. ; 193:2, s. 75-83
  • Tidskriftsartikel (refereegranskat)abstract
    • We consider the problem of maintaining a string of n brackets '('or')' under the operation reverse(i) that changes the ith bracket from '('to')' or vice versa, and returns 'yes' if and only if the resulting string is properly balanced. We show that this problem can be solved on the RAM in time O(log n/log log n) per operation using linear space and preprocessing. Moreover, we show that this is optimal in the sense that every data structure supporting reverse (no matter its space and preprocessing complexity) needs time Omega(Iog n/log log n) per operation in the cell probe model. (C) 2004 Elsevier Inc. All rights reserved.
  •  
4.
  •  
5.
  • Bjorklund, Andreas, et al. (författare)
  • Fast Zeta Transforms for Lattices with Few Irreducibles
  • 2016
  • Ingår i: ACM Transactions on Algorithms. - : Association for Computing Machinery (ACM). - 1549-6325 .- 1549-6333. ; 12:1
  • Tidskriftsartikel (refereegranskat)abstract
    • We investigate fast algorithms for changing between the standard basis and an orthogonal basis of idempotents for Mobius algebras of finite lattices. We show that every lattice with v elements, n of which are nonzero and join-irreducible (or, by a dual result, nonzero and meet-irreducible), has arithmetic circuits of size O(vn) for computing the zeta transform and its inverse, thus enabling fast multiplication in the Mobius algebra. Furthermore, the circuit construction in fact gives optimal (up to constants) monotone circuits for several lattices of combinatorial and algebraic relevance, such as the lattice of subsets of a finite set, the lattice of set partitions of a finite set, the lattice of vector subspaces of a finite vector space, and the lattice of positive divisors of a positive integer.
  •  
6.
  • Björklund, Andreas, et al. (författare)
  • Approximating longest directed paths and cycles
  • 2004
  • Ingår i: Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349. ; 3142, s. 222-233
  • Tidskriftsartikel (refereegranskat)abstract
    • We investigate the hardness of approximating the longest path and the longest cycle in directed graphs on n vertices. We show that neither of these two problems can be polynomial time approximated within n(1-epsilon)for any epsilon > 0 unless P = NP. In particular, the result holds for digraphs of constant bounded outdegree that contain a Hamiltonian cycle. Assuming the stronger complexity conjecture that Satisfiability cannot be solved in subexponential time, we show that there is no polynomial time algorithm that finds a directed path of length Omega(f(n) log(2) n), or a directed cycle of length Omega(f(n) log n), for any nondecreasing, polynomial time computable function f in w(1). With a recent algorithm for undirected graphs by Gabow, this shows that long paths and cycles are harder to find in directed graphs than in undirected graphs. We also find a directed path of length Omega(log(2) n/log log n) in Hamiltonian digraphs with bounded outdegree. With our hardness results, this shows that long directed cycles are harder to find than a long directed paths. Furthermore, we present a simple polynomial time algorithm that finds paths of length Omega(n) in directed expanders of constant bounded outdegree.
  •  
7.
  • Björklund, Andreas, et al. (författare)
  • Computing the permanent modulo a prime power
  • 2017
  • Ingår i: Information Processing Letters. - : Elsevier BV. - 0020-0190. ; 125, s. 20-25
  • Tidskriftsartikel (refereegranskat)abstract
    • We sPRThow how to compute the permanent of an n×n integer matrix modulo pk in time nk+O(1) if p=2 and in time 2n/exp⁡{Ω(γ2n/plog⁡p)} if p is an odd prime with kp0 we can compute the permanent of an n×n integer matrix in time 2n/exp⁡{Ω(δ2n/β1/(1−δ)log⁡β)}, provided there exists a real number β such that |perA|≤βn and β≤(144δn)1−δ.
  •  
8.
  • 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.
  •  
9.
  • Björklund, Andreas, et al. (författare)
  • Counting Connected Subgraphs with Maximum-Degree-Aware Sieving
  • 2018
  • Ingår i: 29th International Symposium on Algorithms and Computation (ISAAC 2018). - 9783959770941 ; , s. 1-17
  • Konferensbidrag (refereegranskat)abstract
    • We study the problem of counting the isomorphic occurrences of a k-vertex pattern graph P as a subgraph in an n-vertex host graph G. Our specific interest is on algorithms for subgraph counting that are sensitive to the maximum degree Delta of the host graph. Assuming that the pattern graph P is connected and admits a vertex balancer of size b, we present an algorithm that counts the occurrences of P in G in O ((2 Delta-2)^{(k+b)/2} 2^{-b} n/(Delta) k^2 log n) time. We define a balancer as a vertex separator of P that can be represented as an intersection of two equal-size vertex subsets, the union of which is the vertex set of P, and both of which induce connected subgraphs of P. A corollary of our main result is that we can count the number of k-vertex paths in an n-vertex graph in O((2 Delta-2)^{floor[k/2]} n k^2 log n) time, which for all moderately dense graphs with Delta <= n^{1/3} improves on the recent breakthrough work of Curticapean, Dell, and Marx [STOC 2017], who show how to count the isomorphic occurrences of a q-edge pattern graph as a subgraph in an n-vertex host graph in time O(q^q n^{0.17q}) for all large enough q. Another recent result of Brand, Dell, and Husfeldt [STOC 2018] shows that k-vertex paths in a bounded-degree graph can be approximately counted in O(4^kn) time. Our result shows that the exact count can be recovered at least as fast for Delta<10. Our algorithm is based on the principle of inclusion and exclusion, and can be viewed as a sparsity-sensitive version of the "counting in halves"-approach explored by Björklund, Husfeldt, Kaski, and Koivisto [ESA 2009].
  •  
10.
  • 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.
  •  
Skapa referenser, mejla, bekava och länka
  • Resultat 1-10 av 50

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Stäng

Kopiera och spara länken för att återkomma till aktuell vy