Russell Martin's publications

• Synchronous rendezvous for location-aware agents.
  A. Collins, J. Czyzowicz, L. Gąsieniec, A. Kosowski, and R. Martin.
  To appear in Proc. 25th International Symposium on Distributed Computing (DISC 2011).
  
  
• Multiprocessor scheduling of unit-sized jobs for speed bounded processors.
  P.C. Bell, P. Chebolu, R. Martin, and P.W.H. Wong.
  Manuscript, 2010.
  
  
• The complexity of approximately counting stable roommate assignments.
  P. Chebolu, L.A. Goldberg, and R. Martin.
  Submitted (2010).
  
  
• Exact counting of Euler tours for generalized series-parallel graphs.
  P. Chebolu, M. Cryan, and R. Martin.
  To appear in Journal of Discrete Algorithms.
  
  
• The complexity of approximately counting stable matchings.
  P. Chebolu, L.A. Goldberg, and R. Martin.
  Proc. 13th Annual International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010),
  Lecture Notes in Computer Science 6302, Springer-Verlag, 2010, pp. 81-94.
  Journal version submitted (October 2010).
  
  
• More efficient periodic traversal in anonymous undirected graphs.
  J. Czyzowicz, S. Dobrev, L. Gąsieniec, D. Ilcinkas, J. Jansson, R. Klasing, I. Lignos, R. Martin, K. Sadakane, and W.-K. Sung.
  Proc. 16th Colloquium on Structural Information and Communication Complexity (SIROCCO 2009),
  Lecture Notes in Computer Science 5869, Springer-Verlag, 2009, pp. 174-188.
  
  
• Fast periodic graph exploration with constant memory.
  L. Gąsieniec, R. Klasing, R. Martin, A. Navarra, and X. Zhang.
  Journal of Computer and System Science 74 (2008), pp. 808-822.
  (Conference version appeared in Proc. 14th Colloquium on Structural Information and Communication Complexity (SIROCCO 2007),
  Lecture Notes in Computer Science 4474, Springer-Verlag, 2007, pp. 26-40.)
  
  
• On the stability of dynamic diffusion load balancing.
  P. Berenbrink, T. Friedetzky, and R. Martin.
  Algorithmica 50 (2008), pp. 329-350.
  
  
• Distributed selfish load balancing.
  P. Berenbrink, T. Friedetzky, L.A. Goldberg, P. Goldberg, Z. Hu, and R. Martin.
  SIAM Journal on Computing 37 (2007), pp. 1163-1181.
  
  
• Reverse Engineering of Web Applications: A Technical Review
  R. Patel, F. Coenen, R. Martin, and L. Archer.
  University of Liverpool Department of Computer Science Technical Report, ULCS-07-017, August 2007.
  
  
• Distributed selfish load balancing.
  P. Berenbrink, T. Friedetzky, L.A. Goldberg, P. Goldberg, Z. Hu, and R. Martin.
  Proc. of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 354-363.
  (Superseded by the 2007 SIAM Journal on Computing paper.)
  
  
• Utilitarian resource assignment.    (PDF)    (Version of March 15, 2005.)
  P. Berenbrink, L.A. Goldberg, P. Goldberg, and R. Martin.
  Journal of Discrete Algorithms 4 (2006), pp. 567--587.
  
  
• Disjoint decomposition of Markov chains and sampling circuits in Cayley graphs.
  R. Martin and D. Randall.
  Combinatorics, Probability, and Computing 15 (2006), pp. 411-448.
  
  
• Markov chain comparison.
  M. Dyer, L.A. Goldberg, M. Jerrum, and R. Martin.
  Probability Surveys 3 (2006), pp. 89-111 (electronic).
  
  
• Improved mixing bounds for the anti-ferromagnetic Potts model on Z^2.
  L.A. Goldberg, M. Jalsenius, M. Paterson, and R. Martin.
  LMS Journal of Computation and Mathematics 9 (2006), pp. 1-20.    (Above link is to the mathematics arXiv, paper math-ph/0507067.)
  
  
• Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows.    (PDF)    (Version of November 18, 2005.)
  M. Cryan, M. Dyer, L.A. Goldberg, M. Jerrum, and R. Martin.
  SIAM Journal on Computing 36 (2006), pp. 247-278 .
  
  
• Dynamic diffusion load balancing.
  P. Berenbrink, T. Friedetzky, and R. Martin.
  Proc. of the 32nd International Colloquium on Automata, Languages, and Programming (ICALP 2005), Lecture Notes in Computer Science 3580, Springer-Verlag, 2005, pp. 1386-1398.
  (Superseded by the 2007 Algorithmica paper entitled "On the stability of dynamic diffusion load balancing".)
  
  
• On weighted balls-into-bins games.
  P. Berenbrink, T. Friedetzky, Z. Hu, and R. Martin.
  Proc. of the 22nd International Symposium on Theoretical Aspects of Computer Science (STACS 2005), pp. 231-243.
  
  
• Strong spatial mixing with fewer colours for lattice graphs.    (PDF)    (Version of April 4, 2005.)
  L.A. Goldberg, R. Martin, and M. Paterson.
  SIAM Journal on Computing 35 (2005), pp. 486-517.
  Short version appears in Proc. of the 45rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004), pp. 562-571.
  
  
• Random sampling of 3-colorings in Z^2.    (PDF)
  L.A. Goldberg, R. Martin, and M. Paterson.
  Random Structures & Algorithms 24 (2004), pp. 279-302.
  
  
• Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows.
  M. Cryan, M. Dyer, L.A. Goldberg, M. Jerrum, and R. Martin.
  Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2002), pp. 711-720.
  (Superseded by the 2006 SIAM Journal on Computing paper.)
  
  
• Paths, Sampling, and Markov Chain Decomposition. (PhD thesis)    (PDF)
  R. Martin, December 2001. (Advisor: Dana Randall)
  
  
• Sampling adsorbing staircase walks using a new Markov chain decomposition method.    (PDF)
  R. Martin and D. Randall.
  Proc. of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2000), pp. 492--502.
  
  
• Pfaffian algorithms for sampling routings on regions with free boundary conditions.    (PDF)
  R. Martin and D. Randall.
  3rd International Workshop on Randomization and Approximation Techniques in Computer Science , Lecture Notes in Computer Science 1671 (1999), pp. 257--268.
  
  
• A core of a block graph.
  R. Laskar and R. Martin.
  Congressus Numerantium 101 (1994), pp. 171--185.
  
  
• Exploring self-duality in graphs.
  C. Depaolo and R. Martin.
  Pi Mu Epsilon Journal 9 (1992), pp. 422--429.
  
  

Note: Where possible I have provided the DOI link to the final published document. You may need subscription access to view some of those papers (usually through your university).
If required, please contact me and I can can provide a version of the paper in most cases.

Back to Russ's home page