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 28
  • [1]23Nästa
Sortera/gruppera träfflistan
   
NumreringReferensOmslagsbildHitta
1.
  • 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*.
  •  
2.
  • 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.
  •  
3.
  • 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.
4.
  • 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.
  •  
5.
  • 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.
  •  
6.
  • 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)
  •  
7.
  • 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)
  •  
8.
  •  
9.
  • Björklund, Andreas, et al. (författare)
  • Exact algorithms for exact satisfiability and number of perfect matchings
  • 2008
  • Ingår i: Algoritmica. - Springer. - 0178-4617. ; 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.
  •  
10.
  • 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). - Springer. - 0302-9743. - 978-3-540-35904-3 ; 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.
  •  
Skapa referenser, mejla, bekava och länka
  • Resultat 1-10 av 28
  • [1]23Nästa
 
pil uppåt Stäng

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