Thore Husfeldt

Petteri Kaski

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

The Presburger Award 2021 - Laudatio for Shayan Oveis Gharan.

[BibT_eX]

[DOI]

Bull. EATCS, 2021

Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths.

[BibT_eX]

[DOI]

Radu Curticapean

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020

The Presburger Award for Young Scientists 2021 - Call for Nominations.

[BibT_eX]

[DOI]

Meena Mahajan

Mikolaj Bojanczyk

Bull. EATCS, 2020

Multivariate Analysis of Orthogonal Range Searching and Graph Distances.

[BibT_eX]

[DOI]

Karl Bringmann

Måns Magnusson

Algorithmica, 2020

Algebraic Algorithms for Finding Patterns in Graphs (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 31st Annual Symposium on Combinatorial Pattern Matching, 2020

2019

Shortest Two Disjoint Paths in Polynomial Time.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

The Presburger Award for Young Scientists 2020 - Call for Nominations.

[BibT_eX]

[DOI]

Meena Mahajan

Anca Muscholl

Bull. EATCS, 2019

2018

Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth.

[BibT_eX]

[DOI]

Karl Bringmann

Måns Magnusson

CoRR, 2018

Extensor-coding.

[BibT_eX]

[DOI]

Cornelius Brand

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Counting Connected Subgraphs with Maximum-Degree-Aware Sieving.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

2017

Narrow sieves for parameterized paths and packings.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2017

Computing the permanent modulo a prime power.

[BibT_eX]

[DOI]

Isak Lyckberg

Inf. Process. Lett., 2017

Guest Editorial: Special Issue on Parameterized and Exact Computation.

[BibT_eX]

[DOI]

Iyad A. Kanj

Algorithmica, 2017

2016

Exact Graph Coloring Using Inclusion-Exclusion.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Fast Zeta Transforms for Lattices with Few Irreducibles.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Computing Graph Distances Parameterized by Treewidth and Diameter.

[BibT_eX]

[DOI]

Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

The First Parameterized Algorithms and Computational Experiments Challenge.

[BibT_eX]

[DOI]

Christian Komusiewicz

Frances A. Rosamond

Proceedings of the 11th International Symposium on Parameterized and Exact Computation, 2016

2015

Graph colouring algorithms.

[BibT_eX]

[DOI]

CoRR, 2015

The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Exponential Time Complexity of the Permanent and the Tutte Polynomial.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2014

2013

Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2013

The Parity of Directed Hamiltonian Cycles.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

The traveling salesman problem in bounded degree graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

Shortest cycle through specified elements.

[BibT_eX]

[DOI]

Nina Taslaman

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Covering and packing in linear space.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2011

Invitation to Algorithmic Uses of Inclusion-Exclusion.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Trimmed Moebius Inversion and Graphs of Bounded Degree.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

Evaluation of permanents in rings and semirings.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2010

Exponential Time Complexity of the Permanent and the Tutte Polynomial.

[BibT_eX]

[DOI]

Martin Wahlen

Electron. Colloquium Comput. Complex., 2010

The Exponential Time Complexity of Computing the Probability That a Graph Is Connected.

[BibT_eX]

[DOI]

Nina Taslaman

Proceedings of the Parameterized and Exact Computation - 5th International Symposium, 2010

10441 Abstracts Collection - Exact Complexity of NP-hard Problems.

[BibT_eX]

[DOI]

Proceedings of the Exact Complexity of NP-hard Problems, 31.10. - 05.11.2010, 2010

2009

Set Partitioning via Inclusion-Exclusion.

[BibT_eX]

[DOI]

Mikko Koivisto

SIAM J. Comput., 2009

On evaluation of permanents

[BibT_eX]

[DOI]

CoRR, 2009

Counting Paths and Packings in Halves.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2009

2008

Exact Graph Coloring Using Inclusion-Exclusion.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

The fast intersection transform with applications to counting paths

[BibT_eX]

[DOI]

CoRR, 2008

Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings.

[BibT_eX]

[DOI]

Algorithmica, 2008

The Travelling Salesman Problem in Bounded Degree Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Computing the Tutte Polynomial in Vertex-Exponential Time.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Fourier meets möbius: fast subset convolution.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

Inclusion-Exclusion Based Algorithms for Graph Colouring.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Inclusion--Exclusion Algorithms for Counting Set Partitions.

[BibT_eX]

[DOI]

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

Black box for constant-time insertion in priority queues (note).

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2005

2004

Dynamic nested brackets.

[BibT_eX]

[DOI]

Stephen Alstrup

Inf. Comput., 2004

Approximating Longest Directed Paths and Cycles.

[BibT_eX]

[DOI]

Sanjeev Khanna

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003

New Lower Bound Techniques for Dynamic Partial Sums and Related Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2003

Finding a Path of Superlogarithmic Length.

[BibT_eX]

[DOI]

SIAM J. Comput., 2003

Approximating Longest Directed Path

[BibT_eX]

[DOI]

Sanjeev Khanna

Electron. Colloquium Comput. Complex., 2003

2002

Lower bounds for approximate polygon decomposition and minimum gap.

[BibT_eX]

[DOI]

Joachim Gudmundsson

Christos Levcopoulos

Inf. Process. Lett., 2002

2001

A cell probe lower bound for dynamic nearest-neighbor searching.

[BibT_eX]

[DOI]

Stephen Alstrup

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

1998

Hardness Results for Dynamic Problems by Extensions of Fredman and Saks' Chronogram Method.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

Marked Ancestor Problems.

[BibT_eX]

[DOI]

Stephen Alstrup

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1996

Lower Bounds for Dynamic Transitive Closure, Planar Point Location, and Parantheses Matching.

[BibT_eX]

Søren Skyum

Nord. J. Comput., 1996

Lower Bounds for Dynamic Transitive Closure, Planar Point Location, and Parentheses Matching.

[BibT_eX]

[DOI]

Gudmund Skovbjerg Frandsen

Søren Skyum

Proceedings of the Algorithm Theory, 1996

1995

Dynamic Algorithms for the Dyck Languages.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

Fully Dynamic Transitive Closure in Plane Dags with One Source and One Sink.

[BibT_eX]

[DOI]