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 36
  • [1]234Nästa
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. - Springer. - 0302-9743. - 978-3-662-43947-0 ; 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. - ACM. - 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. - ACADEMIC PRESS INC ELSEVIER SCIENCE. - 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.
  • Björklund, Andreas, et al. (författare)
  • Approximating longest directed paths and cycles
  • 2004
  • Ingår i: Automata, Languages and Programming. - Springer. - 0302-9743. ; 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.
6.
  • 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. - IEEE Computer Society. - 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.
  •  
7.
  • 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. - Springer. - 0302-9743. ; 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.
  •  
8.
  • 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. - Springer. ; 6198, s. 727-737
  • Konferensbidrag (refereegranskat)
  •  
9.
  • Björklund, Andreas, et al. (författare)
  • Covering and packing in linear space
  • 2011
  • Ingår i: Information Processing Letters. - 0020-0190. ; 111:21–22, s. 1033-1036
  • Tidskriftsartikel (refereegranskat)
  •  
10.
  •  
Skapa referenser, mejla, bekava och länka
  • Resultat 1-10 av 36
  • [1]234Nästa
 
pil uppåt Stäng

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