Martin Furer

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

    Research activity per year

    Filter
    Conference contribution

    Search results

    • 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
    • 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

      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
    • 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
    • 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
    • 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

    • 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
    • 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
    • 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

      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
    • 1995

      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
    • 1994

      Approximating maximum independent set in bounded degree graphs

      Berman, P. & Furer, M., 1994, Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms. Publ by ACM, p. 365-371 7 p. (Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms).

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

      68 Scopus citations
    • 1993

      Coloring random graphs in polynomial expected time

      Furer, M., Subramanian, C. R. & Madhavan, C. E. V., 1993, Algorithms and Computation - 4th International Symposium, ISAAC 1993, Proceedings. Ng, K. W., Raghavan, P., Balasubramanian, N. V. & Chin, F. Y. L. (eds.). Springer Verlag, p. 31-37 7 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 762 LNCS).

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

      6 Scopus citations
    • 1992

      Approximating the minimum degree spanning tree to within one from the optimal degree

      Fürer, M. & Raghavachari, B., Sep 1 1992, Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992. Association for Computing Machinery, p. 317-324 8 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. Part F129721).

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

      93 Scopus citations
    • Coloring random graphs

      Fürer, M. & Subramanian, C. R., 1992, Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings. Nurmi, O. & Ukkonen, E. (eds.). Springer Verlag, p. 284-291 8 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 621 LNCS).

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

      2 Scopus citations
    • O(n log log n)-work parallel algorithms for straight-line grid embeddings of planar graphs

      Fuerer, M., He, X., Kao, M. Y. & Raghavachari, B., Dec 1 1992, 4th Annual ACM Symposium on Parallel Algorithms and Architectures. Publ by ACM, p. 410-419 10 p. (4th Annual ACM Symposium on Parallel Algorithms and Architectures).

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

      4 Scopus citations
    • 1991

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

      Fürer, M. & Raghavachari, B., 1991, Automata, Languages and Programming - 18th International Colloquium, Proceedings. Albert, J. L., Artalejo, M. R. & Monien, B. (eds.). Springer Verlag, p. 429-440 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 510 LNCS).

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

      2 Scopus citations
    • Contracting planar graphs efficiently in parallel

      Fürer, M. & Raghavachari, B., 1991, Foundations of Software Technology and Theoretical Computer Science - 11th Conference, Proceedings. Biswas, S. & Nori, K. V. (eds.). Springer Verlag, p. 319-335 17 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 560 LNCS).

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

    • 1989

      Optimal lower bound on the number of variables for graph identification

      Cai, J. Y., Furer, M. & Immerman, N., 1989, Annual Symposium on Foundations of Computer Science (Proceedings). Publ by IEEE, p. 612-617 6 p. (Annual Symposium on Foundations of Computer Science (Proceedings)).

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

      36 Scopus citations
    • 1988

      Universal hashing in VLSI

      Fürer, M., 1988, VLSI Algorithms and Architectures - 3rd Aegean Workshop on Computing, AWOC 1988, Proceedings. Reif, J. H. (ed.). Springer Verlag, p. 312-318 7 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 319 LNCS).

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

      1 Scopus citations
    • 1987

      Probabilistic quantifiers vs. distrustful adversaries

      Zachos, S. & Furer, M., 1987, Foundations of Software Technology and Theoretical Computer Science - 7th Conference, Proceedings. Nori, K. V. (ed.). Springer Verlag, p. 443-455 13 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 287 LNCS).

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

      22 Scopus citations
    • 1986

      At2-optimal galois field multiplier for VLSI

      Fürer, M. & Mehlhorn, K., 1986, VLSl Algorithms and Architectures - Aegean Workshop on Computing, Proceedings. Mehlhorn, K., Makedon, F., Papatheodorou, T. & Spirakis, P. (eds.). Springer Verlag, p. 217-225 9 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 227 LNCS).

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

      1 Scopus citations
    • 1985

      Deterministic and Las Vegas primality testing algorithms

      Fürer, M., 1985, Automata, Languages and Programming - 12th Colloquium. Brauer, W. (ed.). Springer Verlag, p. 199-209 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 194 LNCS).

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

      3 Scopus citations
    • 1984

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

      Fürer, M., 1984, Logic and Machines: Decision Problems and Complexity - Proceedings of the Symposium Rekursive Kombinatorik. Borger, E., Hasenjaeger, G. & Rodding, D. (eds.). Springer Verlag, p. 312-319 8 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 171 LNCS).

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

      24 Scopus citations
    • 1983

      NORMAL FORMS FOR TRIVALENT GRAPHS AND GRAPHS OF BOUNDED VALENCE.

      Fuerer, M., Schnyder, W. & Specker, E., 1983, Conference Proceedings of the Annual ACM Symposium on Theory of Computing. ACM (Order n 508830), p. 161-170 10 p. (Conference Proceedings of the Annual ACM Symposium on Theory of Computing).

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

      15 Scopus citations
    • 1982

      The tight deterministic time hierarchy

      Fürer, M., May 5 1982, Proceedings of the 14th Annual ACM Symposium on Theory of Computing, STOC 1982. Association for Computing Machinery, p. 8-16 9 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

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

      24 Scopus citations
    • 1980

      The complexity of the inequivalence problem for regular expressions with intersection

      Furer, M., Jan 1 1980, Automata, Languages and Programming - 7th Colloquium. de Bakker, J. & van Leeuwen, J. (eds.). Springer Verlag, p. 234-245 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 85 LNCS).

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

      29 Scopus citations