×
Author ID: fuerer.martin Recent zbMATH articles by "Fürer, Martin"
Published as: Fürer, Martin; Fuerer, Martin; Furer, Martin
Documents Indexed: 75 Publications since 1976, including 1 Book and 1 Additional arXiv Preprint
Co-Authors: 38 Co-Authors with 41 Joint Publications
1,514 Co-Co-Authors

Publications by Year

Citations contained in zbMATH Open

54 Publications have been cited 564 times in 512 Documents Cited by Year
An optimal lower bound on the number of variables for graph identification. Zbl 0785.68043
Cai, Jin-Yi; Fürer, Martin; Immerman, Neil
104
1992
Faster integer multiplication. Zbl 1192.68926
Fürer, Martin
68
2009
Approximation of \(k\)-set cover by semi-local optimization. Zbl 0962.68172
Duh, Rong-chii; Fürer, Martin
56
1999
Approximating the minimum-degree Steiner tree to within one of optimal. Zbl 1321.05262
Fürer, Martin; Raghavachari, Balaji
51
1994
Faster integer multiplication. Zbl 1179.68198
Fürer, Martin
47
2007
Approximating the minimum degree spanning tree to within one from the optimal degree. Zbl 0829.68097
Fürer, Martin; Raghavachari, Balaji
24
1992
Approximating maximum independent set in bounded degree graphs. Zbl 0873.68163
Berman, Piotr; Fürer, Martin
19
1994
The complexity of Presburger arithmetic with bounded quantifier alternation depth. Zbl 0484.03003
Fuerer, Martin
17
1982
On the combinatorial power of the Weisfeiler-Lehman algorithm. Zbl 1489.05146
Fürer, Martin
12
2017
An exponential time 2-approximation algorithm for bandwidth. Zbl 1273.68408
Fürer, Martin; Gaspers, Serge; Kasiviswanathan, Shiva Prasad
11
2009
Approximating the \(k\)-set packing problem by local improvements. Zbl 1452.90264
Fürer, Martin; Yu, Huiwen
11
2014
Probabilistic quantifiers vs. distrustful adversaries. Zbl 0647.68052
Zachos, Stathis; Furer, Martin
10
1987
Algorithms for counting 2-SAT solutions and colorings with applications. Zbl 1137.68620
Fürer, Martin; Kasiviswanathan, Shiva Prasad
10
2007
Faster computation of path-width. Zbl 1478.68238
Fürer, Martin
8
2016
A faster algorithm for finding maximum independent sets in sparse graphs. Zbl 1145.05322
Fürer, Martin
7
2006
Data structures for distributed counting. Zbl 0541.68025
Fürer, Martin
6
1984
Exact Max 2-Sat: Easier and faster. Zbl 1131.68522
Fürer, Martin; Kasiviswanathan, Shiva Prasad
5
2007
Packing-based approximation algorithm for the \(k\)-set cover problem. Zbl 1350.68290
Fürer, Martin; Yu, Huiwen
5
2011
On the power of combinatorial and spectral invariants. Zbl 1217.05141
Fürer, Martin
5
2010
Graph isomorphism testing without numerics for graphs of bounded eigenvalue multiplicity. Zbl 0858.05074
Fürer, Martin
5
1995
Characterizations of bipartite Steinhaus graphs. Zbl 0930.05080
Chang, Gerard J.; DasGupta, Bhaskar; Dymàček, Wayne M.; Fürer, Martin; Koerlin, Matthew; Lee, Yueh-Shin; Whaley, Tom
5
1999
The complexity of the inequivalence problem for regular expressions with intersection. Zbl 0444.68072
Fürer, Martin
5
1980
Solving NP-complete problems with quantum search. Zbl 1136.68519
Fürer, Martin
4
2008
The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems). Zbl 0549.68037
Fürer, Martin
4
1984
Alternation and the Ackermann case of the decision problem. Zbl 0474.03005
Fuerer, Martin
4
1981
Randomized splay trees. Zbl 0929.68085
Fürer, Martin
4
1999
Efficient computation of the characteristic polynomial of a threshold graph. Zbl 1357.05062
Fürer, Martin
4
2017
Spanners for geometric intersection graphs with applications. Zbl 1404.68191
Fürer, Martin; Kasiviswanathan, Shiva Prasad
4
2012
A natural generalization of bounded tree-width and bounded clique-width. Zbl 1405.68246
Fürer, Martin
4
2014
How fast can we multiply large integers on an actual computer? Zbl 1405.68138
Fürer, Martin
4
2014
Improved hardness results for approximating the chromatic number. Zbl 0938.68923
Fürer, Martin
3
1995
Spanners for geometric intersection graphs. Zbl 1209.05241
Fürer, Martin; Kasiviswanathan, Shiva Prasad
3
2007
An almost linear time approximation algorithm for the permanent of a random (0-1) matrix. Zbl 1117.68547
Fürer, Martin; Kasiviswanathan, Shiva Prasad
3
2004
An improvement of Reed’s treewidth approximation. Zbl 07405960
Belbasi, Mahdi; Fürer, Martin
3
2021
Circular permutations and genome shuffling. Zbl 1137.92334
Bafna, Vineet; Beaver, Donald; Fürer, Martin; Pevzner, Pavel A.
2
2000
Weisfeiler-Lehman refinement requires at least a linear number of iterations. Zbl 0986.68039
Fürer, Martin
2
2001
Optimal parallel algorithms for straight-line grid embeddings of planar graphs. Zbl 0813.05021
Kao, Ming-Yang; Fürer, Martin; He, Xin; Raghavachari, Balaji
2
1994
Deterministic and Las Vegas primality testing algorithms. Zbl 0571.10004
Fürer, Martin
2
1985
Approximating permanents of complex matrices. Zbl 1296.65064
Fürer, Martin
2
2000
Space saving by dynamic algebraization based on tree-depth. Zbl 1379.68379
Fürer, Martin; Yu, Huiwen
2
2017
Efficient computation of the characteristic polynomial of a tree and related tasks. Zbl 1360.05083
Fürer, Martin
2
2014
An exponential time 2-approximation algorithm for bandwidth. Zbl 1407.68545
Fürer, Martin; Gaspers, Serge; Kasiviswanathan, Shiva Prasad
2
2013
Eigenvalue location in graphs of small clique-width. Zbl 1402.05136
Fürer, Martin; Hoppen, Carlos; Jacobs, David P.; Trevisan, Vilmar
2
2019
Applications of the linear matroid parity algorithm to approximating Steiner trees. Zbl 1185.68460
Berman, Piotr; Fürer, Martin; Zelikovsky, Alexander
1
2006
Approximate distance queries in disk graphs. Zbl 1129.68587
Fürer, Martin; Kasiviswanathan, Shiva Prasad
1
2007
Coloring random graphs in polynomial expected time. Zbl 0925.05047
Fürer, Martin; Subramanian, C. R.; Veni Madhavan, C. E.
1
1993
Simulation von Turingmaschinen mit logischen Netzen. Zbl 0344.02029
Fürer, Martin
1
1976
Efficient computation of the characteristic polynomial of a tree and related tasks. Zbl 1256.05232
Fürer, Martin
1
2009
Approximately counting embeddings into random graphs. Zbl 1302.05186
Fürer, Martin; Kasiviswanathan, Shiva Prasad
1
2014
Efficient computation of the characteristic polynomial of a threshold graph. Zbl 1410.05094
Fürer, Martin
1
2015
Stathis Zachos at 70! Zbl 1486.68007
Bakali, Eleni; Cheilaris, Panagiotis; Fotakis, Dimitris; Fürer, Martin; Koutras, Costas D.; Markou, Euripides; Nomikos, Christos; Pagourtzis, Aris; Papadimitriou, Christos H.; Papaspyrou, Nikolaos S.; Potika, Katerina
1
2017
A space-efficient parameterized algorithm for the Hamiltonian Cycle problem by dynamic algebraization. Zbl 07121054
Belbasi, Mahdi; Fürer, Martin
1
2019
\(AT^2\)-optimal Galois field multiplier for VLSI. Zbl 1395.68355
Fürer, Martin; Mehlhorn, Kurt
1
1989
Locating the eigenvalues for graphs of small clique-width. Zbl 1485.05100
Fürer, Martin; Hoppen, Carlos; Jacobs, David P.; Trevisan, Vilmar
1
2018
An improvement of Reed’s treewidth approximation. Zbl 07405960
Belbasi, Mahdi; Fürer, Martin
3
2021
Eigenvalue location in graphs of small clique-width. Zbl 1402.05136
Fürer, Martin; Hoppen, Carlos; Jacobs, David P.; Trevisan, Vilmar
2
2019
A space-efficient parameterized algorithm for the Hamiltonian Cycle problem by dynamic algebraization. Zbl 07121054
Belbasi, Mahdi; Fürer, Martin
1
2019
Locating the eigenvalues for graphs of small clique-width. Zbl 1485.05100
Fürer, Martin; Hoppen, Carlos; Jacobs, David P.; Trevisan, Vilmar
1
2018
On the combinatorial power of the Weisfeiler-Lehman algorithm. Zbl 1489.05146
Fürer, Martin
12
2017
Efficient computation of the characteristic polynomial of a threshold graph. Zbl 1357.05062
Fürer, Martin
4
2017
Space saving by dynamic algebraization based on tree-depth. Zbl 1379.68379
Fürer, Martin; Yu, Huiwen
2
2017
Stathis Zachos at 70! Zbl 1486.68007
Bakali, Eleni; Cheilaris, Panagiotis; Fotakis, Dimitris; Fürer, Martin; Koutras, Costas D.; Markou, Euripides; Nomikos, Christos; Pagourtzis, Aris; Papadimitriou, Christos H.; Papaspyrou, Nikolaos S.; Potika, Katerina
1
2017
Faster computation of path-width. Zbl 1478.68238
Fürer, Martin
8
2016
Efficient computation of the characteristic polynomial of a threshold graph. Zbl 1410.05094
Fürer, Martin
1
2015
Approximating the \(k\)-set packing problem by local improvements. Zbl 1452.90264
Fürer, Martin; Yu, Huiwen
11
2014
A natural generalization of bounded tree-width and bounded clique-width. Zbl 1405.68246
Fürer, Martin
4
2014
How fast can we multiply large integers on an actual computer? Zbl 1405.68138
Fürer, Martin
4
2014
Efficient computation of the characteristic polynomial of a tree and related tasks. Zbl 1360.05083
Fürer, Martin
2
2014
Approximately counting embeddings into random graphs. Zbl 1302.05186
Fürer, Martin; Kasiviswanathan, Shiva Prasad
1
2014
An exponential time 2-approximation algorithm for bandwidth. Zbl 1407.68545
Fürer, Martin; Gaspers, Serge; Kasiviswanathan, Shiva Prasad
2
2013
Spanners for geometric intersection graphs with applications. Zbl 1404.68191
Fürer, Martin; Kasiviswanathan, Shiva Prasad
4
2012
Packing-based approximation algorithm for the \(k\)-set cover problem. Zbl 1350.68290
Fürer, Martin; Yu, Huiwen
5
2011
On the power of combinatorial and spectral invariants. Zbl 1217.05141
Fürer, Martin
5
2010
Faster integer multiplication. Zbl 1192.68926
Fürer, Martin
68
2009
An exponential time 2-approximation algorithm for bandwidth. Zbl 1273.68408
Fürer, Martin; Gaspers, Serge; Kasiviswanathan, Shiva Prasad
11
2009
Efficient computation of the characteristic polynomial of a tree and related tasks. Zbl 1256.05232
Fürer, Martin
1
2009
Solving NP-complete problems with quantum search. Zbl 1136.68519
Fürer, Martin
4
2008
Faster integer multiplication. Zbl 1179.68198
Fürer, Martin
47
2007
Algorithms for counting 2-SAT solutions and colorings with applications. Zbl 1137.68620
Fürer, Martin; Kasiviswanathan, Shiva Prasad
10
2007
Exact Max 2-Sat: Easier and faster. Zbl 1131.68522
Fürer, Martin; Kasiviswanathan, Shiva Prasad
5
2007
Spanners for geometric intersection graphs. Zbl 1209.05241
Fürer, Martin; Kasiviswanathan, Shiva Prasad
3
2007
Approximate distance queries in disk graphs. Zbl 1129.68587
Fürer, Martin; Kasiviswanathan, Shiva Prasad
1
2007
A faster algorithm for finding maximum independent sets in sparse graphs. Zbl 1145.05322
Fürer, Martin
7
2006
Applications of the linear matroid parity algorithm to approximating Steiner trees. Zbl 1185.68460
Berman, Piotr; Fürer, Martin; Zelikovsky, Alexander
1
2006
An almost linear time approximation algorithm for the permanent of a random (0-1) matrix. Zbl 1117.68547
Fürer, Martin; Kasiviswanathan, Shiva Prasad
3
2004
Weisfeiler-Lehman refinement requires at least a linear number of iterations. Zbl 0986.68039
Fürer, Martin
2
2001
Circular permutations and genome shuffling. Zbl 1137.92334
Bafna, Vineet; Beaver, Donald; Fürer, Martin; Pevzner, Pavel A.
2
2000
Approximating permanents of complex matrices. Zbl 1296.65064
Fürer, Martin
2
2000
Approximation of \(k\)-set cover by semi-local optimization. Zbl 0962.68172
Duh, Rong-chii; Fürer, Martin
56
1999
Characterizations of bipartite Steinhaus graphs. Zbl 0930.05080
Chang, Gerard J.; DasGupta, Bhaskar; Dymàček, Wayne M.; Fürer, Martin; Koerlin, Matthew; Lee, Yueh-Shin; Whaley, Tom
5
1999
Randomized splay trees. Zbl 0929.68085
Fürer, Martin
4
1999
Graph isomorphism testing without numerics for graphs of bounded eigenvalue multiplicity. Zbl 0858.05074
Fürer, Martin
5
1995
Improved hardness results for approximating the chromatic number. Zbl 0938.68923
Fürer, Martin
3
1995
Approximating the minimum-degree Steiner tree to within one of optimal. Zbl 1321.05262
Fürer, Martin; Raghavachari, Balaji
51
1994
Approximating maximum independent set in bounded degree graphs. Zbl 0873.68163
Berman, Piotr; Fürer, Martin
19
1994
Optimal parallel algorithms for straight-line grid embeddings of planar graphs. Zbl 0813.05021
Kao, Ming-Yang; Fürer, Martin; He, Xin; Raghavachari, Balaji
2
1994
Coloring random graphs in polynomial expected time. Zbl 0925.05047
Fürer, Martin; Subramanian, C. R.; Veni Madhavan, C. E.
1
1993
An optimal lower bound on the number of variables for graph identification. Zbl 0785.68043
Cai, Jin-Yi; Fürer, Martin; Immerman, Neil
104
1992
Approximating the minimum degree spanning tree to within one from the optimal degree. Zbl 0829.68097
Fürer, Martin; Raghavachari, Balaji
24
1992
\(AT^2\)-optimal Galois field multiplier for VLSI. Zbl 1395.68355
Fürer, Martin; Mehlhorn, Kurt
1
1989
Probabilistic quantifiers vs. distrustful adversaries. Zbl 0647.68052
Zachos, Stathis; Furer, Martin
10
1987
Deterministic and Las Vegas primality testing algorithms. Zbl 0571.10004
Fürer, Martin
2
1985
Data structures for distributed counting. Zbl 0541.68025
Fürer, Martin
6
1984
The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems). Zbl 0549.68037
Fürer, Martin
4
1984
The complexity of Presburger arithmetic with bounded quantifier alternation depth. Zbl 0484.03003
Fuerer, Martin
17
1982
Alternation and the Ackermann case of the decision problem. Zbl 0474.03005
Fuerer, Martin
4
1981
The complexity of the inequivalence problem for regular expressions with intersection. Zbl 0444.68072
Fürer, Martin
5
1980
Simulation von Turingmaschinen mit logischen Netzen. Zbl 0344.02029
Fürer, Martin
1
1976
all top 5

Cited by 849 Authors

14 Paschos, Vangelis Th.
13 Fürer, Martin
13 Grohe, Martin
13 Verbitsky, Oleg
11 Harvey, David
10 Dawar, Anuj
10 Escoffier, Bruno
10 Grädel, Erich
9 van der Hoeven, Joris
8 Köbler, Johannes
8 Ponomarenko, Ilya Nikolaevich
8 Saurabh, Saket
7 Kortsarz, Guy
7 Sau, Ignasi
6 Caragiannis, Ioannis
6 Fuhlbrück, Frank
6 Halldórsson, Magnús Mar
6 Neuen, Daniel
6 Nutov, Zeev
5 Bollig, Beate
5 Bourgeois, Nicolas
5 Chen, Yong
5 Gaspers, Serge
5 Kiefer, Sandra
5 Lau, Lap Chi
5 Nagamochi, Hiroshi
5 Otto, Martin
5 Thilikos, Dimitrios M.
5 Xiao, Mingyu
5 Zhang, An
4 Gashkov, Sergey B.
4 Kaklamanis, Christos
4 Karatsuba, Ekaterina Anatol’evna
4 Karpinski, Marek
4 Kolaitis, Phokion G.
4 Lokshtanov, Daniel
4 Pakusa, Wied
4 Pikhurko, Oleg
4 Sergeev, Igor’ Sergeevich
3 Arvind, Vikraman
3 Berkholz, Christoph
3 Bodlaender, Hans L.
3 Chappelon, Jonathan
3 Evdokimov, Sergeĭ Alekseevich
3 Feige, Uriel
3 Hassin, Refael
3 Hella, Lauri T.
3 Huynh, Dung T.
3 Jacobs, David P.
3 Krebs, Andreas
3 Kyropoulou, Maria
3 Lecerf, Grégoire
3 Levin, Asaf
3 Lin, Guohui
3 Lingas, Andrzej
3 Luosto, Kerkko
3 Monnot, Jérôme
3 Motwani, Rajeev
3 Niedermeier, Rolf
3 Nielsen, Frank
3 Okhotin, Alexander
3 Peleg, David
3 Pilipczuk, Michał
3 Raghavachari, Balaji
3 Ravi, Ramamoorthi
3 Schweitzer, Pascal
3 Severini, Simone
3 Sutherland, Andrew V.
3 Szeider, Stefan
3 Tourniaire, Emeric
3 Trevisan, Vilmar
3 Zenklusen, Rico
2 Ailon, Nir
2 Akrida, Eleni C.
2 Allender, Eric W.
2 Amini, Omid
2 An, Min Kyung
2 Anglès d’Auriac, Jean-Alexandre
2 Araújo, Júlio César Silva
2 Athanassopoulos, Stavros
2 Aurora, Pawan Kumar
2 Babai, László
2 Bach, Eric
2 Bafna, Vineet
2 Bakali, Eleni
2 Ballet, Stéphane
2 Barvinok, Alexander I.
2 Bazgan, Cristina
2 Belbasi, Mahdi
2 Berthomieu, Jérémy
2 Blass, Andreas Raphael
2 Blum, Avrim L.
2 Bonnecaze, Alexis
2 Bonnet, Edouard
2 Bostan, Alin
2 Bujtás, Csilla
2 Campos, Victor A.
2 Chandrasekaran, Karthekeyan
2 Chatziafratis, Vaggos
2 Chaudhuri, Kamalika
...and 749 more Authors
all top 5

Cited in 111 Serials

56 Theoretical Computer Science
24 Algorithmica
19 Discrete Applied Mathematics
19 Information Processing Letters
16 Mathematics of Computation
16 Journal of Computer and System Sciences
15 Journal of Combinatorial Optimization
12 Journal of Symbolic Computation
12 Theory of Computing Systems
11 Information and Computation
10 The Journal of Symbolic Logic
9 SIAM Journal on Computing
8 Annals of Pure and Applied Logic
8 SIAM Journal on Discrete Mathematics
8 Journal of Discrete Algorithms
5 Linear Algebra and its Applications
5 Mathematical Programming. Series A. Series B
5 The Bulletin of Symbolic Logic
4 Discrete Mathematics
4 Journal of Graph Theory
4 Journal of Complexity
4 Computational Geometry
4 Discrete Optimization
4 Logical Methods in Computer Science
3 Artificial Intelligence
3 Moscow University Mathematics Bulletin
3 Journal of Combinatorial Theory. Series B
3 Operations Research Letters
3 Graphs and Combinatorics
3 Journal of Parallel and Distributed Computing
3 Computational Complexity
3 Journal of Graph Algorithms and Applications
3 Foundations of Computational Mathematics
3 ACM Transactions on Computational Logic
2 Acta Informatica
2 Mathematical Notes
2 Problems of Information Transmission
2 Journal of Combinatorial Theory. Series A
2 Operations Research
2 European Journal of Combinatorics
2 Discrete & Computational Geometry
2 Journal of Algebraic Combinatorics
2 Journal of Mathematical Sciences (New York)
2 INFORMS Journal on Computing
2 Journal of the ACM
2 Data Mining and Knowledge Discovery
2 LMS Journal of Computation and Mathematics
2 RAIRO. Operations Research
2 Quantum Information Processing
2 Algorithms
2 Theory of Computing
2 Computer Science Review
1 Computers & Mathematics with Applications
1 Journal of Mathematical Physics
1 Applied Mathematics and Computation
1 Archiv der Mathematik
1 Computing
1 Journal of Algebra
1 Journal of Functional Analysis
1 Journal of Number Theory
1 Journal of Pure and Applied Algebra
1 Mathematical Systems Theory
1 Networks
1 Software. Practice & Experience
1 Studia Logica
1 Transactions of the American Mathematical Society
1 Advances in Applied Mathematics
1 Combinatorica
1 Optimization
1 Computers & Operations Research
1 Journal of Automated Reasoning
1 International Journal of Approximate Reasoning
1 Applied Mathematics Letters
1 Journal of Cryptology
1 Japan Journal of Industrial and Applied Mathematics
1 Discrete Mathematics and Applications
1 Automation and Remote Control
1 European Journal of Operational Research
1 Proceedings of the National Academy of Sciences of the United States of America
1 Computational Statistics and Data Analysis
1 Applicable Algebra in Engineering, Communication and Computing
1 The Australasian Journal of Combinatorics
1 Annales de la Faculté des Sciences de Toulouse. Mathématiques. Série VI
1 Journal de Théorie des Nombres de Bordeaux
1 St. Petersburg Mathematical Journal
1 Computational and Applied Mathematics
1 Finite Fields and their Applications
1 The Electronic Journal of Combinatorics
1 Advances in Computational Mathematics
1 International Transactions in Operational Research
1 Journal of Heuristics
1 Constraints
1 ELA. The Electronic Journal of Linear Algebra
1 Mathematical Problems in Engineering
1 Mathematical Methods of Operations Research
1 Chicago Journal of Theoretical Computer Science
1 Journal of Scheduling
1 Sibirskiĭ Zhurnal Vychislitel’noĭ Matematiki
1 Annals of Mathematics. Second Series
1 Internet Mathematics
...and 11 more Serials

Citations by Year