Martin Fürer

J. Graph Algorithms Appl., 2022

2021

Finding All Leftmost Separators of Size ≤k.

[BibT_eX]

[DOI]

CoRR, 2021

Finding All Leftmost Separators of Size $\le k$.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Optimization and Applications, 2021

2020

Efficient Diagonalization of Symmetric Matrices Associated with Graphs of Small Treewidth.

[BibT_eX]

[DOI]

Carlos Hoppen

Vilmar Trevisan

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

A Space-efficient Parameterized Algorithm for the Hamiltonian Cycle Problem by Dynamic Algebraziation.

[BibT_eX]

[DOI]

CoRR, 2019

A Space-Efficient Parameterized Algorithm for the Hamiltonian Cycle Problem by Dynamic Algebraization.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2019

2018

Locating the Eigenvalues for Graphs of Small Clique-Width.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2018: Theoretical Informatics, 2018

2017

Efficient computation of the characteristic polynomial of a threshold graph.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

Space Saving by Dynamic Algebraization Based on Tree-Depth.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2017

Saving Space by Dynamic Algebraization Based on Tree Decomposition: Minimum Dominating Set.

[BibT_eX]

[DOI]

CoRR, 2017

Multi-Clique-Width.

[BibT_eX]

[DOI]

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

On the Combinatorial Power of the Weisfeiler-Lehman Algorithm.

[BibT_eX]

[DOI]

Christos H. Papadimitriou

Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

Stathis Zachos at 70!

[BibT_eX]

[DOI]

Nikolaos S. Papaspyrou

Katerina Potika

Proceedings of the Algorithms and Complexity - 10th International Conference, 2017

2016

Degree-Bounded Trees.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Faster Computation of Path-Width.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 27th International Workshop, 2016

2014

Approximately Counting Embeddings into Random Graphs.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2014

Counting cliques and clique covers in random graphs.

[BibT_eX]

[DOI]

Kashyap Dixit

CoRR, 2014

Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks.

[BibT_eX]

[DOI]

Algorithmica, 2014

How Fast Can We Multiply Large Integers on an Actual Computer?

[BibT_eX]

[DOI]

Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

Approximating the k -Set Packing Problem by Local Improvements.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Optimization - Third International Symposium, 2014

Space Saving by Dynamic Algebraization.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2014

2013

An exponential time 2-approximation algorithm for bandwidth.

[BibT_eX]

[DOI]

Serge Gaspers

Theor. Comput. Sci., 2013

Approximate the k-Set Packing Problem by Local Improvements.

[BibT_eX]

[DOI]

CoRR, 2013

2012

Spanners for geometric intersection graphs with applications.

[BibT_eX]

[DOI]

J. Comput. Geom., 2012

Efficient Arbitrary and Resolution Proofs of Unsatisfiability for Restricted Tree-Width.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

Counting Perfect Matchings in Graphs of Degree 3.

[BibT_eX]

[DOI]

Proceedings of the Fun with Algorithms - 6th International Conference, 2012

2011

Packing-Based Approximation Algorithm for the k-Set Cover Problem.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

2010

Almost Linear Time Computation of the Chromatic Polynomial of a Graph of Bounded Tree-Width.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2010: Theoretical Informatics, 2010

2009

Parallel Computing: Complexity Classes.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Optimization, Second Edition, 2009

Faster Integer Multiplication.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Deterministic Autopoietic Automata

[BibT_eX]

[DOI]

Proceedings of the Proceedings Fifth Workshop on Developments in Computational Models--Computational Models From Nature, 2009

2008

Degree-Bounded Trees.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Solving NP-Complete Problems with Quantum Search.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2008: Theoretical Informatics, 2008

2007

Spanners for Geometric Intersection Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 10th International Workshop, 2007

Exact Max 2-Sat: Easier and Faster.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2007: Theory and Practice of Computer Science, 2007

Algorithms for Counting 2-SatSolutions and Colorings with Applications.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Aspects in Information and Management, 2007

2006

Approximate Distance Queries in Disk Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Applications of the Linear Matroid Parity Algorithm to Approximating Steiner Trees.

[BibT_eX]

[DOI]

Piotr Berman

Alexander Zelikovsky

Proceedings of the Computer Science, 2006

2005

Algorithms for Counting 2-SAT Solutions and Colorings with Applications

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Approximately Counting Perfect Matchings in General Graphs.

[BibT_eX]

[DOI]

Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics, 2005

2004

An Improved Communication-Randomness Tradeo.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2004: Theoretical Informatics, 2004

An Almost Linear Time Approximation Algorithm for the Permanen of a Random (0-1) Matrix.

[BibT_eX]

[DOI]

Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

Quadratic Convergence for Scaling of Matrices.

[BibT_eX]

Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, 2004

2001

Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

2000

Approximating permanents of complex matrices.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

1999

Characterizations of bipartite Steinhaus graphs.

[BibT_eX]

[DOI]

Discret. Math., 1999

Randomized Splay Trees.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998

Algorithms for coloring semi-random graphs.

[BibT_eX]

[DOI]

C. R. Subramanian

C. E. Veni Madhavan

Random Struct. Algorithms, 1998

1997

Approximation of <i>k</i>-Set Cover by Semi-Local Optimization.

[BibT_eX]

[DOI]

Rong-chii Duh

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996

Parallel Edge Coloring Approximation.

[BibT_eX]

[DOI]

Parallel Process. Lett., 1996

Alignment-to-Alignment Editing with "Move Gap" Operations.

[BibT_eX]

[DOI]

Webb Miller

Int. J. Found. Comput. Sci., 1996

1995

An Efficient Parallel Algorithm for Finding Hamiltonian Cycles in Dense Directed Graphs.

[BibT_eX]

[DOI]

J. Algorithms, 1995

Graph Isomorphism Testing without Numberics for Graphs of Bounded Eigenvalue Multiplicity.

[BibT_eX]

[DOI]

Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Improved Hardness Results for Approximating the Chromatic Number.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

Optimal Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 1994

Approximating the Minimum-Degree Steiner Tree to within One of Optimal.

[BibT_eX]

[DOI]

J. Algorithms, 1994

Approximating Maximum Independent Set in Bounded Degree Graphs.

[BibT_eX]

[DOI]

Piotr Berman

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993

Coloring Random Graphs in Polynomial Expected Time.

[BibT_eX]

[DOI]

C. R. Subramanian

C. E. Veni Madhavan

Proceedings of the Algorithms and Computation, 4th International Symposium, 1993

1992

An optimal lower bound on the number of variables for graph identification.

[BibT_eX]

[DOI]

Jin-yi Cai

Neil Immerman

Comb., 1992

Coloring Random Graphs.

[BibT_eX]

[DOI]

C. R. Subramanian

Proceedings of the Algorithm Theory, 1992

O(n log log n)-Work Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992

Approximating the Minimum Degree Spanning Tree to Within One from the Optimal Degree.

[BibT_eX]

[DOI]

Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

1991

An Efficient NC Algorithm for Finding Hamiltonian Cycles in Dense Directed Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

Contracting Planar Graphs Efficiency in Parallel.

[BibT_eX]

[DOI]

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1991

1989

AT²-Optimal Galois Field Multiplier for VLSI.

[BibT_eX]

[DOI]

Kurt Mehlhorn

IEEE Trans. Computers, 1989

On Completeness and Soundness in Interactive Proof Systems.

[BibT_eX]

Adv. Comput. Res., 1989

1988

Universal Hashing in VLSI.

[BibT_eX]

[DOI]

Proceedings of the VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, 1988

1987

The Power of Randomness for Communication Complexity (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Probabalistic Quantifiers vs. Distrustful Adversaries.

[BibT_eX]

[DOI]

Stathis Zachos

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1987

1986

AT<sup>2</sup>-Optimal Galois Field Multiplier for VLSI.

[BibT_eX]

[DOI]

Kurt Mehlhorn

Proceedings of the VLSI Algorithms and Architectures, 1986

1985

Deterministic and Las Vegas Primality Testing Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1985

1984

Data Structures for Distributed Counting.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1984

1983

Normal Forms for Trivalent Graphs and Graphs of Bounded Valence

[BibT_eX]

[DOI]

Walter Schnyder

Ernst Specker

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems).

[BibT_eX]

[DOI]

Proceedings of the Logic and Machines: Decision Problems and Complexity, 1983

1982

The Complexity of Presburger Arithmetic with Bounded Quantifier Alternation Depth.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1982

The Tight Deterministic Time Hierarchy

[BibT_eX]

[DOI]

Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

1980

The Complexity of the Inequivalence Problem for Regular Expressions with Intersection.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1980

1976

Simulation von Turingmaschinen mit logischen Netzen.

[BibT_eX]

[DOI]

Proceedings of the Komplexität von Entscheidungsproblemen, Ein Seminar, 1976

Polynomiale Transformationen und Auswahlaxiom.

[BibT_eX]

[DOI]