Thore Husfeldt

Teaching

DAT010

DAT050

DAT501

Talks

Travels plans

Research

On-line papers

Silly

Danish cryptic crosswords

Sudoku

Thore Husfeldt

News

Papers

The Travelling Salesman Problem in bounded degree graphs
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Part I, LNCS 5125, Springer, 2008, pp. 198–209. submitted manuscript

Trimmed Moebius inversion and graphs of bounded degree
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), Dagstuhl Seminar Proceedings 08001, IBFI Schloss Dagstuhl, 2008, pp. 85–96. [Proceedings version (PDF)]

Computing the Tutte polynomial in vertex-exponential time
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
Proceedings 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2008. [PDF]
Preprint at [arXiv.org].

Fourier meets Möbius: fast subset convolution
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), San Diego, CA, June 11–13, 2007, Association for Computing Machinery, New York, 2007, pp. 67–74. Preprint at [arXiv.org].

Set partitioning via inclusion–exclusion
Andreas Björklund, Thore Husfeldt, and Mikko Koivisto
SIAM J. Comput., Special Issue for FOCS 2006, to appear. [PDF]
The results were announced in two (independent) conference papers at 47th FOCS 2006: Koivisto, An O^*(2ⁿ) algorithm for graph colouring and other partitioning problems via inclusion-exclusion, pp. 583–590; and Björklund and Husfeldt, Inclusion–exclusion algorithms for counting set partitions, pp. 575–582 [PDF], which began its life as ECCC TR06-44.

Exact algorithms for exact satisfiability and number of perfect matchings
Andreas Björklund and Thore Husfeldt
Algorithmica, Volume 52, Number 2, October 2008, pp. 226–249. (DOI 10.1007/s00453-007-9149-8)
Prelim. version in Proc. 33rd ICALP 2006, Springer LNCS 4051, pp. 548–559 [PDF]

Black box for constant-time insertion in priority queues (note)
Stephen Alstrup, Thore Husfeldt, Theis Rauhe, and Mikkel Thorup
ACM Transactions on Algorithms, Vol. 1:1 (July 2005), pp. 102–106. [PDF]

Approximating longest directed paths and cycles
Andreas Björklund, Thore Husfeldt, and Sanjeev Khanna
31st ICALP 2004, Springer LNCS 3142, pp. 222–233. [PDF]

Dynamic nested brackets
Stephen Alstrup, Theis Rauhe, and Thore Husfeldt
Information and Computation, Vol. 193 (2004), No. 6, pp. 75–83. [PDF via ScienceDirect]
Preliminary version: [PDF]

Finding a path of superlogarithmic length
Andreas Björklund and Thore Husfeldt.
SIAM J. Computing. Vol. 32 (2003), No. 6, pp. 1395–1402. [PDF]
Announced at Proc. 29th ICALP 2002, Springer LNCS 2380, pp. 985-992. [DVI, PS, PDF]

Lower bounds for approximate polygon decomposition and minimum gap.
Joachim Gudmundsson, Thore Husfeldt, and Christos Levcopoulos.
IPL 81(3), 2002, pp. 137-141. [PDF]

A cell probe lower bound for dynamic nearest-neighbour searching.
Stephen Alstrup, Thore Husfeldt and Theis Rauhe.
Proc. 12th SODA 2001, pp. 779-780. [PS.GZ]

Marked Ancestor Problems.
Stephen Alstrup, Thore Husfeldt and Theis Rauhe.
Proc. 38th FOCS 1998, pp. 534-543. [PS.GZ]

New lower bound techniques for dynamic partial sums and related problems.
Thore Husfeldt and Theis Rauhe.
SIAM J. Computing. Vol. 32 (2003), No. 3, pp. 736–753. [PDF]
A preliminary version appeared as Hardness Results for Dynamic Problems by Extensions of Fredman and Saks’ Chronogram Method in Proc. 25th ICALP 1998, Springer LNCS 1443, pp. 67-78. [.dvi], [.ps.gz], [.pdf]

Lower Bounds for Dynamic Transitive Closure, Planar Point Location, and Parentheses Matching.
Thore Husfeldt, Theis Rauhe, and Søren Skyum.
Nordic Journal of Computing 3(4):323-336, Winter 1996. Prelim. version in Proc. 5th SWAT 1996, Springer LNCS 1097, pp. 198-211. [PS.GZ]

Fully Dynamic Transitive Closure in Plane Dags with One Source and One Sink.
Thore Husfeldt.
Proc. 3rd European Symposium on Alorithms (ESA), 1995, Springer LNCS 979, pp. 199-212. [PS.GZ]

Dynamic Algorithms for the Dyck Languages.
Gudmund Skovbjerg Frandsen, Thore Husfeldt, Peter Bro Miltersen, Theis Rauhe, and Søren Skyum.
Proc. 4th Workshop on Algorithms and Data Structures (WADS), 1995, Springer LNCS 955, pp. 98-108. [PS.GZ]

A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth.
Gerth Stølting Brodal and Thore Husfeldt.
BRICS Report RS-96-1, 1996. [PS.GZ]

Published Sat, 01 Jan 2000 | News | Permalink