Mary Cryan

Publications

  • "Exact counting of Euler tours and related structures on graphs of bounded treewidth", in preparation (2012). Bounded treewidth case subsumes generalized series-parallel (below)
  • "Exact counting of Euler tours for generalized series-parallel graphs". [arXiv copy].
    Prasad Chebolu, Mary Cryan, and Russ Martin.
    Journal of Discrete Algorithms, 10, pages 110-122, January 2012.
  • "The number of Euler tours of random d-in/d-out graphs".
    Páidí Creed and Mary Cryan
    short version at 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (Analysis of Algorithms 2010), Vienna, Austria, July 2010.
    Proceedings in Discrete Mathematics & Theoretical Computer Science, 2010.
    full version accepted to appear in Electronic Journal on Combinatorics.
  • "Approximately Counting Integral Flows and Cell-Bounded Contingency Tables"
    Mary Cryan, Martin Dyer and Dana Randall
    full version, SIAM Journal on Computing, 39(7), pages 2683-2703, 2010.
    Short version appeared in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 413-422, 2005.
  • "Random Walks on the Vertices of Transportation Polytopes with Constant Number of Sources"
    Mary Cryan, Martin Dyer, Haiko Müller and Leen Stougie
    full version, in Random Structures & Algorithms, 33(3), pages 333-355, 2008.
    Short version appeared in Proceedings of the 14th Annual Symposium on Discrete Algorithms, pages 330-339, 2003.
  • "Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows"
    Mary Cryan, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum and Russell Martin
    full version, SIAM Journal on Computing, 36(1): pages 247-278, 2006.
    short version, Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS 02), pages 711-720, 2002.
  • "A Polynomial-Time Algorithm to Approximately Count Contingency Tables when the Number of Rows is Constant"
    Mary Cryan and Martin Dyer
    full version, Journal of Computer and System Sciences (STOC 2002 Special Issue), 67(2): pages 291-310, 2003.
    short version, Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC 02), pages 240-249, 2002.
  • "On Pseudorandom Generators in NC0"
    Mary Cryan and Peter Bro Miltersen
    short version, Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS 01), Lecture Notes in Computer Science 2136, pages 272-284, Springer-Verlag, 2001.
  • "Learning and Approximation Algorithms for problems motivated by Evolutionary Trees"
    Mary Elizabeth Cryan
    PhD thesis, University of Warwick, awarded Feb 2000.
  • "Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model"
    Mary Cryan, Leslie Ann Goldberg and Paul W. Goldberg
    full version, SIAM Journal on Computing, 31(2): pages 375-397, 2002.
    short version, Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 98), pages 436-445, 1998.
  • "Approximation Algorithms for the Fixed-Topology Phylogenetic Number Problem"
    Mary Cryan, Leslie Ann Goldberg and Cynthia A. Phillips
    full version, Algorithmica, 25(2): pages 311-329, 1999.
    short version, Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching (CPM 97), Lecture Notes in Computer Science 1264, pages 130-149, Springer-Verlag, 1997.
  • "Constructing a normal form for Property Theory"
    Mary Cryan and Allan Ramsay
    Proceedings of the 14th International Conference in Automated Deduction, 1997 (CADE 97), Lecture Notes in Computer Science 1249, pages 237-251, Springer-Verlag, 1997.

email: mcryan AT inf DOT ed DOT ac DOT uk
February 2005