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 11-20 av 50
Sortera/gruppera träfflistan
   
NumreringReferensOmslagsbildHitta
11.
  • Björklund, Andreas, et al. (författare)
  • Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm
  • 2018
  • Ingår i: 29th International Symposium on Algorithms and Computation (ISAAC 2018). - 9783959770941 ; , s. 1-19
  • Konferensbidrag (refereegranskat)abstract
    • Given an undirected graph and two disjoint vertex pairs s_1,t_1 and s_2,t_2, the Shortest two disjoint paths problem (S2DP) asks for the minimum total length of two vertex disjoint paths connecting s_1 with t_1, and s_2 with t_2, respectively. We show that for cubic planar graphs there are NC algorithms, uniform circuits of polynomial size and polylogarithmic depth, that compute the S2DP and moreover also output the number of such minimum length path pairs. Previously, to the best of our knowledge, no deterministic polynomial time algorithm was known for S2DP in cubic planar graphs with arbitrary placement of the terminals. In contrast, the randomized polynomial time algorithm by Björklund and Husfeldt, ICALP 2014, for general graphs is much slower, is serial in nature, and cannot count the solutions. Our results are built on an approach by Hirai and Namba, Algorithmica 2017, for a generalisation of S2DP, and fast algorithms for counting perfect matchings in planar graphs.
  •  
12.
  • 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)
  •  
13.
  • 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)
  •  
14.
  •  
15.
  • 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.
  •  
16.
  • 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.
  •  
17.
  • 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)
  •  
18.
  • 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)
  •  
19.
  • Björklund, Andreas, et al. (författare)
  • Finding a path of superlogarithmic length
  • 2003
  • Ingår i: SIAM Journal on Computing. - 0097-5397. ; 32:6, s. 1395-1402
  • Tidskriftsartikel (refereegranskat)abstract
    • We consider the problem of finding a long, simple path in an undirected graph. We present a polynomial-time algorithm that finds a path of length Omega((log L/log log L)(2)), where L denotes the length of the longest simple path in the graph. This establishes the performance ratio O(n( log log n/log n)(2)) for the longest path problem, where n denotes the number of vertices in the graph.
  •  
20.
  • Björklund, Andreas, et al. (författare)
  • Finding a path of superlogarithmic length
  • 2002
  • Ingår i: Automata, languages and programming : 29th international colloquium, ICALP 2002, Málaga, Spain, July 8-13, 2002 : proceedings. - 3540438645 ; LNCS 2380, s. 985-992
  • Konferensbidrag (refereegranskat)abstract
    • We consider the problem of nding a long, simple path in anundirected graph.W e present a polynomial-time algorithm that ndsa path of length (log L/ log log L)2, where L denotes the length ofthe longest simple path in the graph.This establishes the performanceratio O|V |(log log |V |/ log |V |)2 for the Longest Path problem, whereV denotes the graphs vertices.
  •  
Skapa referenser, mejla, bekava och länka
  • Resultat 11-20 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