---

Copyright Notice: Most of these papers are published, the copyright has been transferred to the respective publishers. Therefore, the papers cannot be duplicated for commercial purposes without the written permission from the respective publishers.

---

M. Fürer, A counterexample in graph isomorphism testing, Tech. Rep. CS­-87-­36,
Dept. of Computer Science, Pennsylvania State University, 1987. (Pdf, 11 pages,  940 KB)

M. Fürer. Weisfeiler-Lehman Refinement Requires at Least a Linear Number of
Iterations. Proceedings of the Twenty-Eighth International Colloquium on Automata,
Languages and Programming (ICALP 2001). Edited by F. Orejas, P. G. Spirakis, J. van
Leeuwen. Springer-Verlag LNCS 2076:322-333. Crete, Greece, July 2001.
(Pdf, 12 pages,  184 KB)

---

• G. J. Chang, B. DasGupta, W. M. Dymacek, M. Fürer, M. Koerlin, Y.-S. Lee, and T. Whaley. Characterizations of bipartite steinhaus graphs. Discrete Mathematics, 1999. Accepted for publication, May 1998.

• Martin Fürer. Randomized splay trees. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, Maryland, 17-19 January 1999. (PostScript, 2 pages, 85202 bytes) (DVI, 35824 bytes)

• Martin Fürer. Randomized splay trees. Technical Report CSE-98-013, Department of Computer Science and Engineering, Pennsylvania State University, July 1998. (PostScript, 10 pages, 168357 bytes) (DVI, 13460 bytes)

• C.R. Subramanian, Martin Fürer, and C.E. Veni Madhavan. Algorithms for coloring semi-random graphs. Random Structures & Algorithms, 13(2):125-158, September 1998.

• Rong-chii Duh and Martin Fürer. Approximation of k-set cover by semi-local optimization. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 256-264, El Paso, Texas, 4-6 May 1997. (PostScript, 9 pages, 272933 bytes)

• Martin Fürer and Webb Miller. Alignment-to-alignment editing with ``move gap'' operations. International Journal of Foundations of Computer Science, Special Issue on Algorithmic Aspects of Computational Biology, 7(1):23-41, March 1996.

• M. Fürer and B. Raghavachari. Parallel edge coloring approximation. Parallel Processing Letters, 6(3):321-329, September 1996. (PostScript, 8 pages, 165339 bytes)

• Martin Fürer. Graph isomorphism testing without numberics for graphs of bounded eigenvalue multiplicity. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 624-631, San Francisco, California, 22-24 January 1995. (PostScript, 9 pages, 155226 bytes)

• Martin Fürer. Improved hardness results for approximating the chromatic number. In 36th Annual Symposium on Foundations of Computer Science, pages 414-421, Milwaukee, Wisconsin, 23-25 October 1995. IEEE. (PostScript, 8 pages, 168441 bytes)

• Martin Fürer and Balaji Raghavachari. An efficient parallel algorithm for finding Hamiltonian cycles in dense directed graphs. Journal of Algorithms, 18(2):203-220, March 1995.

• Piotr Berman and Martin Fürer. Approximating maximum independent set in bounded degree graphs. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 365-371, Arlington, VA, January 1994. ACM Press. (PostScript, 7 pages, 151464 bytes)

• Martin Fürer and Balaji Raghavachari. Approximating the minimum-degree Steiner tree to within one of optimal. Journal of Algorithms, 17(3):409-423, November 1994. (PostScript, 13 pages, 173617 bytes)

• Ming-Yang Kao, Martin Fürer, Xin He, and Balaji Raghavachari. Optimal parallel algorithms for straight-line grid embeddings of planar graphs. SIAM Journal on Discrete Mathematics, 7(4):632-646, November 1994.

• Fürer, Subramanian, and Madhavan. Coloring random graphs in polynomial expected time. In ISAAC: 4th International Symposium on Algorithms and Computation (formerly SIGAL International Symposium on Algorithms), volume 762 of Lecture Notes in Computer Science, pages 31-37. Springer-Verlag, 1993.

• J. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12:389-410, 1992. (PostScript, 31 pages, 348502 bytes)

• Martin Fürer and Balaji Raghavachari. Approximating the minimum degree spanning tree to within one from the optimal degree. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '92), pages 317-324, Orlando, FL, USA, January 1992. SIAM.

• Martin Fürer and C. R. Subramanian. Coloring random graphs. In Algorithm Theory---SWAT '92: Third Scandinavian Workshop on Algorithm Theory, volume 621 of Lecture Notes in Computer Science, pages 284-291, Helsinki, Finland, 8-10 July 1992. Springer-Verlag.

• Martin Fürer, Xin He, Ming-Yang Kao, and Balaji Raghavachari. O(n log log n)-work parallel algorithms for straight-line grid embeddings of planar graphs. In Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 410-419, San Diego, California, June 29-July 1, 1992. SIGACT/SIGARCH.

• M. Fürer and B. Raghavachari. An efficient NC algorithm for finding hamiltonian cycles in dense directed graphs. In Proceedings of Automata, Languages and Programming (ICALP '91), volume 510 of LNCS, pages 429-440, Berlin, Germany, July 1991. Springer.

• Martin Fürer and Balaji Raghavachari. Contracting planar graphs efficiently in parallel. In Proceedings of Foundations of Software Technology and Theoretical Computer Science, volume 560 of LNCS, pages 319-335, Berlin, Germany, December 1991. Springer.

• Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. In 30th Annual Symposium on Foundations of Computer Science, pages 612-617, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

• Fürer and Mehlhorn. AT²-optimal galois field multiplier for VLSI. IEEE Transactions on Computers, 38:1333-1336, 1989.

• M. Furer, O. Goldreich, Y. Mansour, M. Sipser, and S. Zachos. On completeness and soundness in interactive proof systems. In S. Micali, editor, Advances in Computing Research 5: Randomness and Computation, pages 429-442. JAI Press, Greenwich, CT, 1989.

• M. Fürer. Universal hashing in VLSI. In Aegean Workshop on Computing (3rd: 1988: Kerkyra, Corfu Island, Greece) VLSI algorithms and architectures: 3rd Aegean Workshop on Computing, AWOC 88, Corfu, Greece, June 28-July 1, 1988: proceedings, pages 312-318, Berlin, Germany / Heidelberg, Germany / London, UK / etc., June 1988. Springer-Verlag.

• M. Fürer. The power of randomness for computational complexity. In Proc. 19th Ann. ACM Symp. on Theory of Computing, pages 178-181, 1987.

• Martin Fürer. The power of randomness for communication complexity (preliminary version). In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pages 178-181, New York City, 25-27 May 1987.

• S. Zachos and M. Fürer. Probabilistic quantifiers vs. distrustful adversaries. In Proceedings of the 7th Conference on Foundations of Software Technology and Theoretical Computer Science, volume 287 of LNCS, pages 443-455, Pune, India, December 1987. Springer.

• Martin Fürer and Kurt Mehlhorn. AT²-optimal Galois field multiplier for VLSI. In AWOC: Aegean Workshop on Computing: VLSI Algorithms and Architectures, volume 227, pages 217-225. LNCS, Springer-Verlag, 1986.

• M. Fürer. Deterministic and Las Vegas primality testing algorithms. In Proceedings of the 12th Colloquium on Automata, Languages and Programming, volume 194 of LNCS, pages 199-209, Nafplion, Greece, July 1985. Springer.

• Martin Fürer. Data structures for distributed counting. Journal of Computer and System Sciences, 28(2):231-243, April 1984.

• Martin Fürer, Walter Schnyder, and Ernst Specker. Normal forms for trivalent graphs and graphs of bounded valence. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pages 161-170, Boston, Massachusetts, 25-27 April 1983.

• Fürer. The complexity of Presburger arithmetic with bounded quantifier alternation depth (note). TCS: Theoretical Computer Science, 18(1):105-111, 1982.

• M. Fürer. Alternation and the Ackermann case of the decision problem. In Logic and Algorithmic: An International Symposium Held in Honour of Ernst Specker, pages 161-186. L'Enseignement Mathematique, Universite de Genève, 1982.

• Martin Fürer. The tight deterministic time hierarchy. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 8-16, San Francisco, California, 5-7 May 1982.

• M. Fürer. Alternation and the Ackermann case of the decision problem. L'Enseignment Mathematique, 27:137-162, 1981.

• Martin Fürer. The complexity of the inequivalence problem for regular expressions with intersection. In Automata, Languages and Programming, 7th Colloquium, volume 85 of Lecture Notes in Computer Science, pages 234-245, Noordweijkerhout, The Netherland, 14-18 July 1980. Springer-Verlag.

• M. Fürer. Polynomiale Transformationen und Auswahlaxiom. In Ernst Specker and Volker Strassen, editors, Komplexität von Entscheidungsproblemen: ein Seminar, volume 43 of LNCS, pages 86-101. Springer, 1976.

• M. Fürer. Simulation von Turingmaschinen mit logischen Netzen. In Ernst Specker and Volker Strassen, editors, Komplexität von Entscheidungsproblemen: ein Seminar, volume 43 of LNCS, pages 163-181. Springer, 1976.