Martin Fürer

Publication Activity (10 Years)

Years Active: 1976-2022
Publications (10 Years): 22

Top Topics

Bounded Treewidth

Grow Exponentially

Packing Problem

Top Venues

Theor. Comput. Sci.

Publications

Mahdi Belbasi, Martin Fürer
An Improvement of Reed's Treewidth Approximation. J. Graph Algorithms Appl. 26 (2) (2022)
Mahdi Belbasi, Martin Fürer
An Improvement of Reed's Treewidth Approximation. WALCOM (2021)
Mahdi Belbasi, Martin Fürer
Finding All Leftmost Separators of Size $\le k$. COCOA (2021)
Martin Fürer, Carlos Hoppen, Vilmar Trevisan
Efficient diagonalization of symmetric matrices associated with graphs of small treewidth. CoRR (2021)
Mahdi Belbasi, Martin Fürer
Finding All Leftmost Separators of Size ≤k. CoRR (2021)
Mahdi Belbasi, Martin Fürer
An Improvement of Reed's Treewidth Approximation. CoRR (2020)
Martin Fürer, Carlos Hoppen, Vilmar Trevisan
Efficient Diagonalization of Symmetric Matrices Associated with Graphs of Small Treewidth. ICALP (2020)
Mahdi Belbasi, Martin Fürer
A Space-efficient Parameterized Algorithm for the Hamiltonian Cycle Problem by Dynamic Algebraziation. CoRR (2019)
Mahdi Belbasi, Martin Fürer
A Space-Efficient Parameterized Algorithm for the Hamiltonian Cycle Problem by Dynamic Algebraization. CSR (2019)
Martin Fürer, Carlos Hoppen, David Pokrass Jacobs, Vilmar Trevisan
Locating the Eigenvalues for Graphs of Small Clique-Width. LATIN (2018)
Martin Fürer
Multi-Clique-Width. ITCS (2017)
Eleni Bakali, Panagiotis Cheilaris, Dimitris Fotakis, Martin Fürer, Costas D. Koutras, Euripides Markou, Christos Nomikos, Aris Pagourtzis, Christos H. Papadimitriou, Nikolaos S. Papaspyrou, Katerina Potika
Stathis Zachos at 70! CIAC (2017)
Martin Fürer
Efficient computation of the characteristic polynomial of a threshold graph. Theor. Comput. Sci. 657 (2017)
Mahdi Belbasi, Martin Fürer
Saving Space by Dynamic Algebraization Based on Tree Decomposition: Minimum Dominating Set. CoRR (2017)
Martin Fürer, Huiwen Yu
Space Saving by Dynamic Algebraization Based on Tree-Depth. Theory Comput. Syst. 61 (2) (2017)
Martin Fürer
On the Combinatorial Power of the Weisfeiler-Lehman Algorithm. CIAC (2017)
Martin Fürer
On the Combinatorial Power of the Weisfeiler-Lehman Algorithm. CoRR (2017)
Martin Fürer
Faster Computation of Path-Width. CoRR (2016)
Martin Fürer
Faster Computation of Path-Width. IWOCA (2016)
Martin Fürer
Efficient Computation of the Characteristic Polynomial of a Threshold Graph. FAW (2015)
Martin Fürer
Multi-Clique-Width. CoRR (2015)
Martin Fürer
Efficient Computation of the Characteristic Polynomial of a Threshold Graph. CoRR (2015)
Martin Fürer
How Fast Can We Multiply Large Integers on an Actual Computer? LATIN (2014)
Martin Fürer
How Fast Can We Multiply Large Integers on an Actual Computer? CoRR (2014)
Martin Fürer
A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width. CoRR (2014)
Martin Fürer, Huiwen Yu
Space Saving by Dynamic Algebraization. CoRR (2014)
Martin Fürer, Huiwen Yu
Approximating the k -Set Packing Problem by Local Improvements. ISCO (2014)
Martin Fürer, Huiwen Yu
Space Saving by Dynamic Algebraization. CSR (2014)
Martin Fürer
A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width. LATIN (2014)
Martin Fürer, Shiva Prasad Kasiviswanathan
Approximately Counting Embeddings into Random Graphs. Comb. Probab. Comput. 23 (6) (2014)
Martin Fürer
Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks. Algorithmica 68 (3) (2014)
Kashyap Dixit, Martin Fürer
Counting cliques and clique covers in random graphs. CoRR (2014)
Martin Fürer, Serge Gaspers, Shiva Prasad Kasiviswanathan
An exponential time 2-approximation algorithm for bandwidth. Theor. Comput. Sci. 511 (2013)
Martin Fürer, Huiwen Yu
Approximate the k-Set Packing Problem by Local Improvements. CoRR (2013)
Martin Fürer
Deterministic Autopoietic Automata. Int. J. Softw. Informatics 7 (4) (2013)
Martin Fürer, Shiva Prasad Kasiviswanathan
Spanners for geometric intersection graphs with applications. J. Comput. Geom. 3 (1) (2012)
Martin Fürer
Efficient Arbitrary and Resolution Proofs of Unsatisfiability for Restricted Tree-Width. LATIN (2012)
Martin Fürer
Counting Perfect Matchings in Graphs of Degree 3. FUN (2012)
Martin Fürer, Huiwen Yu
Packing-Based Approximation Algorithm for the k-Set Cover Problem CoRR (2011)
Martin Fürer, Huiwen Yu
Packing-Based Approximation Algorithm for the k-Set Cover Problem. ISAAC (2011)
Martin Fürer
Almost Linear Time Computation of the Chromatic Polynomial of a Graph of Bounded Tree-Width. LATIN (2010)
Martin Fürer, Serge Gaspers, Shiva Prasad Kasiviswanathan
An Exponential Time 2-Approximation Algorithm for Bandwidth CoRR (2009)
Martin Fürer, Serge Gaspers, Shiva Prasad Kasiviswanathan
An Exponential Time 2-Approximation Algorithm for Bandwidth. IWPEC (2009)
Martin Fürer
Deterministic Autopoietic Automata DCM (2009)
Martin Fürer
Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks. ESA (2009)
Martin Fürer
Faster Integer Multiplication. SIAM J. Comput. 39 (3) (2009)
Martin Fürer
Solving NP-Complete Problems with Quantum Search. LATIN (2008)
Martin Fürer, Shiva Prasad Kasiviswanathan
Approximately Counting Embeddings into Random Graphs CoRR (2008)
Martin Fürer, Shiva Prasad Kasiviswanathan
Approximately Counting Embeddings into Random Graphs. APPROX-RANDOM (2008)
Martin Fürer
Faster integer multiplication. STOC (2007)
Martin Fürer, Shiva Prasad Kasiviswanathan
Algorithms for Counting 2-SatSolutions and Colorings with Applications. AAIM (2007)
Martin Fürer, Shiva Prasad Kasiviswanathan
Spanners for Geometric Intersection Graphs. WADS (2007)
Martin Fürer, Shiva Prasad Kasiviswanathan
Exact Max 2-Sat: Easier and Faster. SOFSEM (1) (2007)
Piotr Berman, Martin Fürer, Alexander Zelikovsky
Applications of the Linear Matroid Parity Algorithm to Approximating Steiner Trees. CSR (2006)
Martin Fürer, Shiva Prasad Kasiviswanathan
Spanners for Geometric Intersection Graphs CoRR (2006)
Martin Fürer
A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs. LATIN (2006)
Martin Fürer, Shiva Prasad Kasiviswanathan
Approximate Distance Queries in Disk Graphs. WAOA (2006)
Martin Fürer, Shiva Prasad Kasiviswanathan
Algorithms for Counting 2-SAT Solutions and Colorings with Applications Electron. Colloquium Comput. Complex. (033) (2005)
Martin Fürer, Shiva Prasad Kasiviswanathan
Approximately Counting Perfect Matchings in General Graphs. ALENEX/ANALCO (2005)
Martin Fürer
Quadratic Convergence for Scaling of Matrices. ALENEX/ANALC (2004)
Martin Fürer, Shiva Prasad Kasiviswanathan
An Almost Linear Time Approximation Algorithm for the Permanen of a Random (0-1) Matrix. FSTTCS (2004)
Martin Fürer
An Improved Communication-Randomness Tradeo. LATIN (2004)
Martin Fürer
Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations. ICALP (2001)
Martin Fürer
Approximating permanents of complex matrices. STOC (2000)
Gerard J. Chang, Bhaskar DasGupta, Wayne M. Dymàcek, Martin Fürer, Matthew Koerlin, Yueh-Shin Lee, Tom Whaley
Characterizations of bipartite Steinhaus graphs. Discret. Math. 199 (1-3) (1999)
Martin Fürer
Randomized Splay Trees. SODA (1999)
C. R. Subramanian, Martin Fürer, C. E. Veni Madhavan
Algorithms for coloring semi-random graphs. Random Struct. Algorithms 13 (2) (1998)
Rong-chii Duh, Martin Fürer
-Set Cover by Semi-Local Optimization. STOC (1997)
Martin Fürer, Balaji Raghavachari
Parallel Edge Coloring Approximation. Parallel Process. Lett. 6 (3) (1996)
Martin Fürer, W. Miller
Alignment-to-Alignment Editing with "Move Gap" Operations. Int. J. Found. Comput. Sci. 7 (1) (1996)
Martin Fürer
Improved Hardness Results for Approximating the Chromatic Number. FOCS (1995)
Martin Fürer
Graph Isomorphism Testing without Numberics for Graphs of Bounded Eigenvalue Multiplicity. SODA (1995)
Martin Fürer, Balaji Raghavachari
An Efficient Parallel Algorithm for Finding Hamiltonian Cycles in Dense Directed Graphs. J. Algorithms 18 (2) (1995)
Martin Fürer, Balaji Raghavachari
Approximating the Minimum-Degree Steiner Tree to within One of Optimal. J. Algorithms 17 (3) (1994)
Ming-Yang Kao, Martin Fürer, Xin He, Balaji Raghavachari
Optimal Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs. SIAM J. Discret. Math. 7 (4) (1994)
Piotr Berman, Martin Fürer
Approximating Maximum Independent Set in Bounded Degree Graphs. SODA (1994)
Martin Fürer, C. R. Subramanian, C. E. Veni Madhavan
Coloring Random Graphs in Polynomial Expected Time. ISAAC (1993)
Martin Fürer, Balaji Raghavachari
Approximating the Minimum Degree Spanning Tree to Within One from the Optimal Degree. SODA (1992)
Martin Fürer, C. R. Subramanian
Coloring Random Graphs. SWAT (1992)
Martin Fürer, Xin He, Ming-Yang Kao, Balaji Raghavachari
O(n log log n)-Work Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs. SPAA (1992)
Jin-yi Cai, Martin Fürer, Neil Immerman
An optimal lower bound on the number of variables for graph identifications. Comb. 12 (4) (1992)
Martin Fürer
An Efficient NC Algorithm for Finding Hamiltonian Cycles in Dense Directed Graphs. ICALP (1991)
Martin Fürer
Contracting Planar Graphs Efficiency in Parallel. FSTTCS (1991)
Jin-yi Cai, Martin Fürer, Neil Immerman
An Optimal Lower Bound on the Number of Variables for Graph Identification FOCS (1989)
Martin Fürer, Oded Goldreich, Yishay Mansour, Michael Sipser, Stathis Zachos
On Completeness and Soundness in Interactive Proof Systems. Adv. Comput. Res. 5 (1989)
Martin Fürer, Kurt Mehlhorn
AT²-Optimal Galois Field Multiplier for VLSI. IEEE Trans. Computers 38 (9) (1989)
Martin Fürer
Universal Hashing in VLSI. AWOC (1988)
Martin Fürer
The Power of Randomness for Communication Complexity (Preliminary Version) STOC (1987)
Stathis Zachos, Martin Fürer
Probabalistic Quantifiers vs. Distrustful Adversaries. FSTTCS (1987)
Martin Fürer, Kurt Mehlhorn
-Optimal Galois Field Multiplier for VLSI. Aegean Workshop on Computing (1986)
Martin Fürer
Deterministic and Las Vegas Primality Testing Algorithms. ICALP (1985)
Martin Fürer
Data Structures for Distributed Counting. J. Comput. Syst. Sci. 28 (2) (1984)
Martin Fürer, Walter Schnyder, Ernst Specker
Normal Forms for Trivalent Graphs and Graphs of Bounded Valence STOC (1983)
Martin Fürer
The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems). Logic and Machines (1983)
Martin Fürer
The Complexity of Presburger Arithmetic with Bounded Quantifier Alternation Depth. Theor. Comput. Sci. 18 (1982)
Martin Fürer
The Tight Deterministic Time Hierarchy STOC (1982)
Martin Fürer
The Complexity of the Inequivalence Problem for Regular Expressions with Intersection. ICALP (1980)
Martin Fürer
Polynomiale Transformationen und Auswahlaxiom. Komplexität von Entscheidungsproblemen 1976 (1976)
Martin Fürer
Simulation von Turingmaschinen mit logischen Netzen. Komplexität von Entscheidungsproblemen 1976 (1976)