John Michael Robson

CoRR, 2021

2020

Robustness: A new form of heredity motivated by dynamic networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

2019

Counting in one-hop beeping networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2019

Design patterns in beeping algorithms: Examples, emulation, and analysis.

[BibT_eX]

[DOI]

Inf. Comput., 2019

Deterministic Leader Election Takes Θ(D+log n) Bit Rounds.

[BibT_eX]

[DOI]

Algorithmica, 2019

2017

Robustness in Highly Dynamic Networks.

[BibT_eX]

[DOI]

CoRR, 2017

2016

Randomised distributed MIS and colouring algorithms for rings with oriented edges in O(√(log n)) bit rounds.

[BibT_eX]

[DOI]

Inf. Comput., 2016

A distributed enumeration algorithm and applications to all pairs shortest paths, diameter...

[BibT_eX]

[DOI]

Inf. Comput., 2016

Deterministic Leader Election in O(D+\log n) Time with Messages of Size O(1).

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 30th International Symposium, 2016

Design Patterns in Beeping Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 20th International Conference on Principles of Distributed Systems, 2016

2015

Analysis of fully distributed splitting and naming probabilistic procedures and applications.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

On Distributed Computing with Beeps.

[BibT_eX]

[DOI]

CoRR, 2015

2014

On Lower Bounds for the Time and the Bit Complexity of Some Probabilistic Distributed Graph Algorithms - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2014: Theory and Practice of Computer Science, 2014

2013

On the time and the bit complexity of distributed randomised anonymous ring colouring.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings.

[BibT_eX]

[DOI]

Inf. Comput., 2013

Analysis of Fully Distributed Splitting and Naming Probabilistic Procedures and Applications - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2013

2012

On the Number of Indecomposable Permutations with a Given Number of Cycles.

[BibT_eX]

[DOI]

Robert Cori

Claire Mathieu

Electron. J. Comb., 2012

2011

An optimal bit complexity randomized distributed MIS algorithm.

[BibT_eX]

[DOI]

Distributed Comput., 2011

2010

About randomised distributed graph colouring and graph partition algorithms.

[BibT_eX]

[DOI]

Inf. Comput., 2010

Uniform election in trees and polyominoids.

[BibT_eX]

[DOI]

Abdelaaziz El Hibaoui

Discret. Appl. Math., 2010

2009

An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2009

Brief Annoucement: Analysis of an Optimal Bit Complexity Randomised Distributed Vertex Colouring Algorithm.

[BibT_eX]

[DOI]

Proceedings of the Principles of Distributed Systems, 13th International Conference, 2009

2008

Spanning Trees of Bounded Degree Graphs.

[BibT_eX]

[DOI]

Proceedings of the Moderately Exponential Time Algorithms, 19.10. - 24.10.2008, 2008

2006

Efficient Simulations by Queue Machines.

[BibT_eX]

[DOI]

Holger Petersen

SIAM J. Comput., 2006

2002

Constant bounds on the moments of the height of binary search trees.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

2001

Hard Tiling Problems with Simple Tiles.

[BibT_eX]

[DOI]

Cristopher Moore

Discret. Comput. Geom., 2001

2000

Deterministic Radio Broadcasting.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

On Recognizing Cayley Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2000

1999

Separating Words with Small Grammars.

[BibT_eX]

[DOI]

J. Autom. Lang. Comb., 1999

On Quadratic Word Equations.

[BibT_eX]

[DOI]

Volker Diekert

Proceedings of the STACS 99, 1999

1997

Automaticity II: Descriptional Complexity in the Unary Case.

[BibT_eX]

[DOI]

Carl Pomerance

Jeffrey O. Shallit

Theor. Comput. Sci., 1997

On the Concentration of the Height of Binary Search Trees.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 24th International Colloquium, 1997

1996

Fast and Scalable Parallel Algorithms for Knapsack-like Problems.

[BibT_eX]

[DOI]

Afonso Ferreira

J. Parallel Distributed Comput., 1996

Separating Words with Machines and Groups.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1996

1995

On the Generation of Random Binary Search Trees.

[BibT_eX]

[DOI]

Luc Devroye

SIAM J. Comput., 1995

1993

Analytic Variations on Quadtrees.

[BibT_eX]

[DOI]

Algorithmica, 1993

1992

Deterministic Simulation of a Single Tape Turing Machine by a Random Access Machine in Sub-linear Time

[BibT_eX]

[DOI]

Inf. Comput., July, 1992

More Languages of Generalised Star Height 1.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1992

Transitive Closure in Parallel on a Linear Network of Processors.

[BibT_eX]

[DOI]

Michel Gastaldo

Michel Morvan

Parallel Process. Lett., 1992

1991

An O (T log T) Reduction from RAM Computations to Satisfiability.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1991

The Analysis of Multidimensional Searching in Quad-Trees.

[BibT_eX]

[DOI]

Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1991

1990

Strong Time Bounds: Non-Computable Bounds and a Hierarchy Theorem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1990

Random Access Machines with Multi-Dimensional Memories.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1990

RAM with Compact Memory: A Realistic and Robust Model of Computation.

[BibT_eX]

[DOI]

Etienne Grandjean

Proceedings of the Computer Science Logic, 4th Workshop, 1990

1989

Separating Strings with Small Automata.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1989

1986

Algorithms for Maximum Independent Sets.

[BibT_eX]

[DOI]

J. Algorithms, 1986

1985

Alternation with Restrictions on Looping

[BibT_eX]

[DOI]

Inf. Control., 1985

1984

N by N Checkers is Exptime Complete.

[BibT_eX]

[DOI]

SIAM J. Comput., 1984

Fast Probabilistic RAM Simulation of Single Tape Turing Machine Computations

[BibT_eX]

[DOI]

Inf. Control., 1984

Combinatorial Games with Exponential Space Complete Decision Problems.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

1983

The Complexity of Go.

[BibT_eX]

Proceedings of the Information Processing 83, 1983

1980

Storage Allocation is NP-Hard.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1980

1979

The Emptiness of Complement Problem for Semi Extended Regular Expressions Requires c<sup>n</sup> Space.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1979

The Height of Binary Search Trees.

[BibT_eX]

Aust. Comput. J., 1979

1977

Worst Case Fragmentation of First Fit and Best Fit Storage Allocation Strategies.

[BibT_eX]

[DOI]

Comput. J., 1977

A Bounded Storage Algorithm for Copying Cyclic Structures.

[BibT_eX]

[DOI]

Commun. ACM, 1977

1975

A Simple Solution to the Interleaved Memory Bandwidth Problem.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1975

1974

Bounds for Some Functions Concerning Dynamic Storage Allocation.

[BibT_eX]

[DOI]

J. ACM, 1974

1973

An Improved Algorithm for Traversing Binary Trees Without Auxiliary Stack.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1973

1971

An Estimate of the Store Size Necessary for Dynamic Storage Allocation.

[BibT_eX]

[DOI]

J. ACM, 1971

1969

Algorithm 362: generation of random permutations [G6].

[BibT_eX]

[DOI]