## 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^{*}(2^{n}) 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]