Thore Husfeldt

Publications

Graph Colouring Algorithms
Thore Husfeldt.
Chapter XIII of \emph{Topics in Chromatic Graph Theory}, L. W. Beineke and Robin J. Wilson (eds.), Encyclopedia of Mathematics and its Applications, Cambridge University Press, ISBN 978-1-107-03350-4, 2015, pp. 277–303. [author-typeset version].

Shortest two disjoint paths in polynomial time
Andreas Björklund and Thore Husfeldt.
ICALP 2014, to appear.
Proceedings version, rev. e5d5661

The parity of directed Hamiltonian cycles
Andreas Björklund and Thore Husfeldt.
54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA. IEEE Computer Society 2013, pp. 727-735.
arXiv:1301.7250v2

Exponential time complexity of the permanent and the Tutte polynomial
Holger Dell, Thore Husfeldt, Daniél Marx, Nina Taslaman, and Martin Wahlén
ACM Transactions on Algorithms, to appear. arXiv:1206.1775v1
Subsumes and expands conference papers at ICALP 2010 and IPEC 2010 (see below).

Fast zeta transforms for lattices with few irreducibles
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, and Pekka Parviainen
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012, Kyoto, 17–19 January, 2012), to appear. [proceedings version]

Shortest Cycle Through Specified Elements
Andreas Björklund, Thore Husfeldt, and Nina Taslaman
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012, Kyoto, 17–19 January, 2012), to appear. [submission]

Invitation to algorithmic uses of inclusion–exclusion
Thore Husfeldt
38th International Colloquium on Automata, Languages and Programming (ICALP 2011), Zürich, Switzerland, July 4-8, 2011, Part II, Springer LNCS 6756, 2011, pages 42-59. arXiv:1105.2942

The exponential time complexity of computing the probability that a graph is connected
Thore Husfeldt, Nina Taslaman
5th International Symposium on Parameterized and Exact Computation (IPEC 2010), December 13–15, 2010, Chennai, India. Springer LNCS 6478, 2010, pages 192-203. arXiv:1009.2363.

Exponential time complexity of the permanent and the Tutte polynomial
Holger Dell, Thore Husfeldt, and Martin Wahlén
37th International Colloquium on Automata, Languages and Programming (ICALP 2010), Bordeaux, France, July 6-10, 2010, Springer LNCS 6198, 2010, pages 426-437.
Full paper at ECCC TR10-78

Covering and packing in linear space.
Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
37th International Colloquium on Automata, Languages and Programming (ICALP 2010), Bordeaux, France, July 6-10, 2010, Springer LNCS 6198, 2010, pages 727-737. [proceedings version]

Evaluation of permanents in rings and semirings
Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
Inform. Proc. Lett. 110:867–870 (2010). DOI 10.1016/j.ipl.2010.07.005 [online at publisher’s site]
Preliminary version: On evaluation of permanents. arXiv 0904.3251

Counting paths and packings in halves.
Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto
17th Annual European Symposium on Algorithms (ESA 2009), LNCS 5757, Springer, 2009, pp. 578–586.
Preliminary version: arXiv 0904.3093

The Travelling Salesman Problem in bounded degree graphs
Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto
Transactions on Algorithms, to appear. Prelim. version in 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
Theory Comput. Syst. 47(3): 637-654 (2010)
Announced at 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. Volume 39, Issue 2, (special issue for FOCS 2006), pp. 546-563 (2009). DOI: 10.1137/070683933. [PDF]
The results were announced in two (independent) conference papers at 47th FOCS 2006: Koivisto, An O*(2n) 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]

Written by thorehusfeldt

August 15, 2010 at 15:20

%d bloggers like this: