Russell Martin's publications

• The Match-Maker: Constant-space distributed majority via random walks.
  L. Gąsieniec, D.D. Hamilton, R. Martin, and P.G. Spirakis.
  Submitted.
  
  
• Deterministic Symmetry Breaking in Ring Networks.
  L. Gąsieniec, T. Jurdzinski, R. Martin, and G. Stachowiak.
  Accpeted to 35th IEEE International Conference on Distributed Computing.
  
  
• Group search on the line.
  M. Chrobak, L. Gąsieniec, T. Gorry, and R. Martin.
  41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2015), pp.164-176.
  
  
• Evacuating robots from an unknown exit in a disk.
  J. Czyzowicz, L. Gąsieniec, T. Gorry, E. Kranakis, R. Martin, and D. Pająk.
  28th International Symposium on Distributed Computing (DISC 2014), pp. 122-136.
  
  
• A scalable algorithm for banded pattern mining in multi-dimensional zero-one data.
  F.B. Abdullahi, F. Coenen, and R. Martin.
  Data Warehousing and Knowledge Discovery - 16th International Conference (DaWaK 2014), pp. 345-356.
  
  
• A novel approach for identifying banded patterns in zero-one data using column and row banding scores.
  F.B. Abdullahi, F. Coenen, and R. Martin.
  Machine Learning and Data Mining in Pattern Recognition - 10th International Conference (MLDM 2014), pp. 58-72.
  
  
• Optimal patrolling of fragmented boundaries.
  A. Collins, J. Czyzowicz, L. Gąsieniec, A. Kosowski, E. Kranakis, D. Krizanc, R. Martin, and O. Morales Ponce.
  Proc. 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2013)., pp. 241-250.
  
  
• Observe and remain silent (Communication-less agent location discovery).
  T. Friedetzky, L. Gąsieniec, T. Gorry, and R. Martin.
  Proc. 37th International Symposium on Mathematical Foundations of Computer Science (MFCS 2012),
  Lecture Notes in Computer Science 7464, Springer-Verlag, 2012, pp. 407-418.
  
  
• Geometric computations by broadcasting automata.
  R. Martin, T. Nickson, and I. Potapov.
  Natural Computing 11 (2012), pp. 623-635.
  (Conference version appeared in Proc. 10th International Conference on Unconventional Computing (UC 2011), pp. 138-151.)
  
  
• 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.
  Theoretical Computer Science 444 (2012), pp. 60-76.
  (Conference version appeared in Proc. 16th Colloquium on Structural Information and Communication Complexity (SIROCCO 2009),
  Lecture Notes in Computer Science 5869, Springer-Verlag, 2009, pp. 174-188.)
  
  
• The complexity of approximately counting stable roommate assignments.
  P. Chebolu, L.A. Goldberg, and R. Martin.
  Journal of Computer and System Sciences 78 (2012), pp. 1579-1605.
  
  
• The complexity of approximately counting stable matchings.
  P. Chebolu, L.A. Goldberg, and R. Martin.
  Theoretical Computer Science 437 (2012), pp. 35-68.
  (Conference version appeared in 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.)
  
  
• Exact counting of Euler tours for generalized series-parallel graphs.
  P. Chebolu, M. Cryan, and R. Martin.
  Journal of Discrete Algorithms 10 (2012), pp. 110-122..
  
  
• Synchronous rendezvous for location-aware agents.
  A. Collins, J. Czyzowicz, L. Gąsieniec, A. Kosowski, and R. Martin.
  Proc. 25th International Symposium on Distributed Computing (DISC 2011),
  Lecture Notes in Computer Science 6950, Springer-Verlag, 2011, pp. 447-459.
  
  
• Geometric computations by broadcasting automata on the integer grid.
  R. Martin, T. Nickson, and I. Potapov.
  Proc. 10th International Conference on Unconventional Computation (UC 2011),
  Lecture Notes in Computer Science 6714, Springer-Verlag, 2011, pp. 138-151.
  
  
• Multiprocessor scheduling of unit-sized jobs for speed bounded processors.
  P.C. Bell, P. Chebolu, R. Martin, and P.W.H. Wong.
  Manuscript, 2010.
  
  
• 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.
  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.   
  
  
• 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.
  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.   
  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.
  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.
  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.
  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