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 to35th 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 Science7464, Springer-Verlag, 2012, pp. 407-418.

- Geometric computations by broadcasting automata.

R. Martin, T. Nickson, and I. Potapov.

Natural Computing11(2012), pp. 623-635.

(Conference version appeared inProc. 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 Science444(2012), pp. 60-76.

(Conference version appeared inProc. 16th Colloquium on Structural Information and Communication Complexity (SIROCCO 2009),

Lecture Notes in Computer Science5869, 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 Sciences78(2012), pp. 1579-1605.

- The complexity of approximately counting stable matchings.

P. Chebolu, L.A. Goldberg, and R. Martin.

Theoretical Computer Science437(2012), pp. 35-68.

(Conference version appeared inProc. 13th Annual International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010),

Lecture Notes in Computer Science6302, 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 Algorithms10(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 Science6950, 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 Science6714, 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 Science74(2008), pp. 808-822.

(Conference version appeared inProc. 14th Colloquium on Structural Information and Communication Complexity (SIROCCO 2007),

Lecture Notes in Computer Science4474, Springer-Verlag, 2007, pp. 26-40.)

- On the stability of dynamic diffusion load balancing.

P. Berenbrink, T. Friedetzky, and R. Martin.

Algorithmica50(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 Computing37(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 2007SIAM Journal on Computingpaper.)

- Utilitarian resource assignment.

P. Berenbrink, L.A. Goldberg, P. Goldberg, and R. Martin.

Journal of Discrete Algorithms4(2006), pp. 567--587.

- Disjoint decomposition of Markov chains and sampling circuits in Cayley graphs.

R. Martin and D. Randall.

Combinatorics, Probability, and Computing15(2006), pp. 411-448.

- Markov chain comparison.

M. Dyer, L.A. Goldberg, M. Jerrum, and R. Martin.

Probability Surveys3(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 Mathematics9(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 Computing36(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 2007Algorithmicapaper 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 Computing35(2005), pp. 486-517.

Short version appears inProc. 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 & Algorithms24(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 2006SIAM Journal on Computingpaper.)

- 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 Science1671(1999), pp. 257--268.

- A core of a block graph.

R. Laskar and R. Martin.

Congressus Numerantium101(1994), pp. 171--185.

- Exploring self-duality in graphs.

C. Depaolo and R. Martin.

Pi Mu Epsilon Journal9(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