Martin Furer

    Calculated based on number of publications stored in Pure and citations from Scopus
    1980 …2022

    Research activity per year

    Search results

    • 2022

      An Improvement of Reed’s Treewidth Approximation

      Belbasi, M. & Fürer, M., 2022, In: Journal of Graph Algorithms and Applications. 26, 2, p. 257-282 26 p.

      Research output: Contribution to journalArticlepeer-review

      Open Access
      2 Scopus citations
    • 2021

      An Improvement of Reed’s Treewidth Approximation

      Belbasi, M. & Fürer, M., 2021, WALCOM: Algorithms and Computation - 15th International Conference and Workshops, WALCOM 2021, Proceedings. Uehara, R., Hong, S.-H. & Nandy, S. C. (eds.). Springer Science and Business Media Deutschland GmbH, p. 166-181 16 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12635 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      1 Scopus citations
    • Finding All Leftmost Separators of Size ≤ k

      Belbasi, M. & Fürer, M., 2021, Combinatorial Optimization and Applications - 15th International Conference, COCOA 2021, Proceedings. Du, D.-Z., Du, D., Wu, C. & Xu, D. (eds.). Springer Science and Business Media Deutschland GmbH, p. 273-287 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 13135 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      1 Scopus citations
    • 2020

      Efficient diagonalization of symmetric matrices associated with graphs of small treewidth

      Fürer, M., Hoppen, C. & Trevisan, V., Jun 1 2020, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020. Czumaj, A., Dawar, A. & Merelli, E. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 52. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 168).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      1 Scopus citations
    • 2019

      A space-efficient parameterized algorithm for the hamiltonian cycle problem by dynamic algebraization

      Belbasi, M. & Fürer, M., 2019, Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings. van Bevern, R. & Kucherov, G. (eds.). Springer Verlag, p. 38-49 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11532 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      4 Scopus citations
    • Eigenvalue location in graphs of small clique-width

      Fürer, M., Hoppen, C., Jacobs, D. P. & Trevisan, V., Jan 1 2019, In: Linear Algebra and Its Applications. 560, p. 56-85 30 p.

      Research output: Contribution to journalArticlepeer-review

      Open Access
      5 Scopus citations
    • 2018

      Locating the eigenvalues for graphs of small clique-width

      Fürer, M., Hoppen, C., Jacobs, D. P. & Trevisan, V., 2018, LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Proceedings. Mosteiro, M. A., Bender, M. A. & Farach-Colton, M. (eds.). Springer Verlag, p. 475-489 15 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10807 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      3 Scopus citations
    • 2017

      Efficient computation of the characteristic polynomial of a threshold graph

      Fürer, M., Jan 2 2017, In: Theoretical Computer Science. 657, p. 3-10 8 p.

      Research output: Contribution to journalArticlepeer-review

      Open Access
      5 Scopus citations
    • Space Saving by Dynamic Algebraization Based on Tree-Depth

      Fürer, M. & Yu, H., Aug 1 2017, In: Theory of Computing Systems. 61, 2, p. 283-304 22 p.

      Research output: Contribution to journalArticlepeer-review

      10 Scopus citations
    • Stathis zachos at 70!

      Bakali, E., Cheilaris, P., Fotakis, D., Fürer, M., Koutras, C. D., Markou, E., Nomikos, C., Pagourtzis, A., Papadimitriou, C. H., Papaspyrou, N. S. & Potika, K., 2017, Algorithms and Complexity - 10th International Conference, CIAC 2017, Proceedings. Fotakis, D., Pagourtzis, A. & Paschos, V. T. (eds.). Springer Verlag, p. 469-484 16 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10236 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

    • 2016

      Faster computation of path-width

      Fürer, M., 2016, Combinatorial Algorithms - 27th International Workshop, IWOCA 2016, Proceedings. Mäkinen, V., Puglisi, S. J. & Salmela, L. (eds.). Springer Verlag, p. 385-396 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9843 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      11 Scopus citations
    • 2015

      Efficient computation of the characteristic polynomial of a threshold graph

      Fürer, M., 2015, Frontiers in Algorithmics - 9th International Workshop, FAW 2015, Proceedings. Yap, C. & Wang, J. (eds.). Springer Verlag, p. 45-51 7 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 9130).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      1 Scopus citations
    • 2014

      A natural generalization of bounded tree-width and bounded clique-width

      Fürer, M., 2014, LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Springer Verlag, p. 72-83 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8392 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      Open Access
      7 Scopus citations
    • Approximately counting embeddings into random graphs

      Fürer, M. & Kasiviswanathan, S. P., Nov 2 2014, In: Combinatorics Probability and Computing. 23, 6, p. 1028-1056 29 p.

      Research output: Contribution to journalArticlepeer-review

      Open Access
      3 Scopus citations
    • Approximating the k-Set Packing problem by local improvements

      Fürer, M. & Yu, H., 2014, Combinatorial Optimization - Third International Symposium, ISCO 2014, Revised Selected Papers. Springer Verlag, p. 408-420 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8596 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      26 Scopus citations
    • Efficient computation of the characteristic polynomial of a tree and related tasks

      Fürer, M., Mar 2014, In: Algorithmica. 68, 3, p. 626-642 17 p.

      Research output: Contribution to journalArticlepeer-review

      5 Scopus citations
    • How fast can we multiply large integers on an actual computer?

      Fürer, M., 2014, LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Springer Verlag, p. 660-670 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8392 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      Open Access
      9 Scopus citations
    • Space saving by dynamic algebraization

      Fürer, M. & Yu, H., 2014, Computer Science Theory and Applications - 9th International Computer Science Symposium in Russia, CSR 2014, Proceedings. Springer Verlag, p. 375-388 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8476 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      Open Access
      4 Scopus citations
    • 2013

      An exponential time 2-approximation algorithm for bandwidth

      Fürer, M., Gaspers, S. & Kasiviswanathan, S. P., Nov 4 2013, In: Theoretical Computer Science. 511, p. 23-31 9 p.

      Research output: Contribution to journalArticlepeer-review

      Open Access
      4 Scopus citations
    • 2012

      Counting perfect matchings in graphs of degree 3

      Furer, M., 2012, Fun with Algorithms - 6th International Conference, FUN 2012, Proceedings. p. 189-197 9 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7288 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      1 Scopus citations
    • Efficient arbitrary and resolution proofs of unsatisfiability for restricted tree-width

      Fürer, M., 2012, LATIN 2012: Theoretical Informatics - 10th Latin American Symposium, Proceedings. p. 387-398 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7256 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

    • 2011

      Packing-based approximation algorithm for the k-set cover problem

      Fürer, M. & Yu, H., 2011, Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings. p. 484-493 10 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7074 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      Open Access
      5 Scopus citations
    • 2010

      Almost linear time computation of the chromatic polynomial of a graph of bounded tree-width

      Furer, M., 2010, LATIN 2010: Theoretical Informatics - 9th Latin American Symposium, Proceedings. p. 49-59 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6034 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

    • On the power of combinatorial and spectral invariants

      Fürer, M., Apr 15 2010, In: Linear Algebra and Its Applications. 432, 9, p. 2373-2380 8 p.

      Research output: Contribution to journalArticlepeer-review

      Open Access
      13 Scopus citations
    • 2009

      An exponential time 2-approximation algorithm for bandwidth

      Fürer, M., Gaspers, S. & Kasiviswanathan, S. P., 2009, Parameterized and Exact Computation - 4th International Workshop, IWPEC 2009, Revised Selected Papers. p. 173-184 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5917 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      Open Access
      15 Scopus citations
    • Deterministic autopoietic automata

      Fürer, M., Nov 15 2009, In: Electronic Proceedings in Theoretical Computer Science, EPTCS. 9, p. 49-53 5 p.

      Research output: Contribution to journalConference articlepeer-review

      Open Access
    • Efficient computation of the characteristic polynomial of a tree and related tasks

      Fürer, M., 2009, Algorithms - ESA 2009 - 17th Annual European Symposium, Proceedings. p. 11-22 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5757 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      2 Scopus citations
    • 2008

      Approximately counting embeddings into random graphs

      Fürer, M. & Kasiviswanathan, S. P., 2008, Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings. p. 416-429 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5171 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      Open Access
      3 Scopus citations
    • Solving NP-complete problems with quantum search

      Fürer, M., 2008, LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings. p. 784-792 9 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4957 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      10 Scopus citations
    • 2007

      Algorithms for counting 2-SAT solutions and colorings with applications

      Fürer, M. & Kasiviswanathan, S. P., 2007, Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings. Springer Verlag, p. 47-57 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4508 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      21 Scopus citations
    • Approximate distance queries in disk graphs

      Fürer, M. & Kasiviswanathan, S. P., 2007, Approximation and Online Algorithms - 4th International Workshop, WAOA 2006, Revised Papers. Springer Verlag, p. 174-187 14 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4368 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      2 Scopus citations
    • Exact MAX 2-SAT: Easier and faster

      Fürer, M. & Kasiviswanathan, S. P., 2007, SOFSEM 2007: Theory and Practice of Computer Science - 33rd Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Springer Verlag, p. 272-283 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4362 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      5 Scopus citations
    • Faster integer multiplication

      Fürer, M., 2007, STOC'07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. p. 57-66 10 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      131 Scopus citations
    • Spanners for geometric intersection graphs

      Fürer, M. & Kasiviswanathan, S. P., 2007, Algorithms and Data Structures - 10th International Workshop, WADS 2007, Proceedings. Springer Verlag, p. 312-324 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 4619 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      7 Scopus citations
    • 2006

      A faster algorithm for finding maximum independent sets in sparse graphs

      Fürer, M., 2006, LATIN 2006: Theoretical Informatics - 7th Latin American Symposium, Proceedings. Springer Verlag, p. 491-501 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 3887 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      19 Scopus citations
    • 5 Scopus citations
    • 2005

      Approximately counting perfect matchings in general graphs

      Fürer, M. & Kasiviswanathan, S. P., 2005, Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics. Demetrescu, C., Sedgewick, R. & Tamassia, R. (eds.). p. 263-272 10 p. (Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithms and Combinatorics).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      3 Scopus citations
    • 2004
      6 Scopus citations
    • An improved communication-randomness tradeoff

      Fürer, M., 2004, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Farach-Colton, M. (ed.). Springer Verlag, p. 444-454 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2976).

      Research output: Chapter in Book/Report/Conference proceedingChapter

    • Quadratic convergence for scaling of matrices

      Fürer, M., Nov 22 2004, Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algoritms and Combinatorics. Arge, L., Italiano, G. F. & Sedgewick, R. (eds.). p. 216-223 8 p. (Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithms and Combinatorics).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      4 Scopus citations
    • 2001

      Weisfeiler-lehman refinement requires at least a linear number of iterations

      Fürer, M., 2001, Automata, Languages and Programming - 28th International Colloquium, ICALP 2001, Proceedings. Orejas, F., Spirakis, P. G. & van Leeuwen, J. (eds.). Springer Verlag, p. 322-333 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 2076 LNCS).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      21 Scopus citations
    • 2000

      Approximating permanents of complex matrices

      Fürer, M., 2000, Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000. p. 667-669 3 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      2 Scopus citations
    • 1999

      Characterizations of bipartite Steinhaus graphs

      Chang, G. J., DasGupta, B., Dymàček, W. M., Fürer, M., Koerlin, M., Lee, Y. S. & Whaley, T., Mar 28 1999, In: Discrete Mathematics. 199, 1-3, p. 11-25 15 p.

      Research output: Contribution to journalArticlepeer-review

      Open Access
      6 Scopus citations
    • Randomized splay trees

      Furer, M., Jan 1 1999, p. S903-S904.

      Research output: Contribution to conferencePaperpeer-review

      20 Scopus citations
    • 1998

      Algorithms for coloring semi-random graphs

      Subramanian, C. R., Furer, M. & Veni Madhavan, C. E., Jan 1 1998, In: Random Structures and Algorithms. 13, 2, p. 125-158 34 p.

      Research output: Contribution to journalArticlepeer-review

      7 Scopus citations
    • 1997

      Approximation of k-Set Cover by semi-local optimization

      Duh, R. C. & Furer, M., 1997, In: Conference Proceedings of the Annual ACM Symposium on Theory of Computing. p. 256-264 9 p.

      Research output: Contribution to journalConference articlepeer-review

      Open Access
      128 Scopus citations
    • 1996

      Parallel edge coloring approximation

      Fürer, M., 1996, In: Parallel Processing Letters. 6, 3, p. 321-329 9 p.

      Research output: Contribution to journalArticlepeer-review

      5 Scopus citations
    • 1995

      An efficient parallel algorithm for finding hamiltonian cycles in dense directed graphs

      Furer, M. & Raghavachari, B., Jan 1 1995, In: Journal of Algorithms. 18, 2, p. 203-220 18 p.

      Research output: Contribution to journalArticlepeer-review

    • Graph isomorphism testing without numerics for graphs of bounded eigenvalue multiplicity

      Fürer, M., Jan 22 1995, Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995. Association for Computing Machinery, p. 624-631 8 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

      Research output: Chapter in Book/Report/Conference proceedingConference contribution

      8 Scopus citations
    • Improved hardness results for approximating the chromatic number

      Furer, M., Dec 1 1995, In: Annual Symposium on Foundations of Computer Science - Proceedings. p. 414-421 8 p.

      Research output: Contribution to journalConference articlepeer-review

      19 Scopus citations