Lawrence L. Larmore

Theor. Comput. Sci., October, 2023

Analysis of a memory-efficient self-stabilizing BFS spanning tree construction.

[BibT_eX]

[DOI]

Theor. Comput. Sci., April, 2023

2020

Loosely-stabilizing leader election with polylogarithmic convergence time.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Self-stabilizing token distribution on trees with constant space.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 2020

Election in unidirectional rings with homonyms.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 2020

Linear time distributed swap edge algorithms.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2020

2019

Loosely-Stabilizing Leader Election for Arbitrary Graphs in Population Protocol Model.

[BibT_eX]

[DOI]

IEEE Trans. Parallel Distributed Syst., 2019

A silent self-stabilizing algorithm for the generalized minimal k-dominating set problem.

[BibT_eX]

[DOI]

Ajoy K. Datta

Theor. Comput. Sci., 2019

Analysis of a Memory-Efficient Self-Stabilizing BFS Spanning Tree.

[BibT_eX]

[DOI]

CoRR, 2019

Brief Announcement: Analysis of a Memory-Efficient Self-stabilizing BFS Spanning Tree Construction.

[BibT_eX]

[DOI]

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2019

2018

Constant Space Self-stabilizing Center Finding Algorithms in Chains and Trees.

[BibT_eX]

[DOI]

Parallel Process. Lett., 2018

Self-Stabilizing Leader Election in Dynamic Networks.

[BibT_eX]

[DOI]

Ajoy K. Datta

Theory Comput. Syst., 2018

Constant-Space Self-stabilizing Token Distribution in Trees.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2018

Self-Stabilizing Token Distribution with Constant-Space for Trees.

[BibT_eX]

[DOI]

Proceedings of the 22nd International Conference on Principles of Distributed Systems, 2018

2017

Self-stabilizing silent disjunction in an anonymous network.

[BibT_eX]

[DOI]

Ajoy K. Datta

Theor. Comput. Sci., 2017

Self-Stabilizing Weak Leader Election in Anonymous Trees Using Constant Memory per Edge.

[BibT_eX]

[DOI]

Parallel Process. Lett., 2017

Brief Announcement: Reduced Space Self-stabilizing Center Finding Algorithms in Chains and Trees.

[BibT_eX]

[DOI]

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2017

Leader Election in Asymmetric Labeled Unidirectional Rings.

[BibT_eX]

[DOI]

Proceedings of the 2017 IEEE International Parallel and Distributed Processing Symposium, 2017

A Self-Stabilizing Minimal k-Grouping Algorithm.

[BibT_eX]

[DOI]

Proceedings of the 18th International Conference on Distributed Computing and Networking, 2017

2016

Competitive self-stabilizing k-clustering.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Leader Election in Rings with Bounded Multiplicity (Short Paper).

[BibT_eX]

[DOI]

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2016

The Same Speed Timer in Population Protocols.

[BibT_eX]

[DOI]

Proceedings of the 36th IEEE International Conference on Distributed Computing Systems, 2016

2015

R-LINE: A better randomized 2-server algorithm on the line.

[BibT_eX]

[DOI]

Lucas Bang

Theor. Comput. Sci., 2015

Self-stabilizing (f, g)-alliances with safe convergence.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 2015

Maximum Matching for Anonymous Trees with Constant Space per Process.

[BibT_eX]

[DOI]

Toshimitsu Masuzawa

Proceedings of the 19th International Conference on Principles of Distributed Systems, 2015

Enabling Ring Exploration with Myopic Oblivious Robots.

[BibT_eX]

[DOI]

Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium Workshop, 2015

Constant Space Self-Stabilizing Center Finding in Anonymous Tree Networks.

[BibT_eX]

[DOI]

Toshimitsu Masuzawa

Proceedings of the 2015 International Conference on Distributed Computing and Networking, 2015

Self-Stabilizing ℓ-Exclusion Revisited.

[BibT_eX]

[DOI]

Proceedings of the 2015 International Conference on Distributed Computing and Networking, 2015

2014

A Communication-Efficient Self-stabilizing Algorithm for Breadth-First Search Trees.

[BibT_eX]

[DOI]

Toshimitsu Masuzawa

Proceedings of the Principles of Distributed Systems - 18th International Conference, 2014

2013

Self-stabilizing labeling and ranking in ordered trees.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Self-Stabilizing Small k-Dominating Sets.

[BibT_eX]

[DOI]

Int. J. Netw. Comput., 2013

Ring Exploration by Oblivious Robots with Vision Limited to 2 or 3.

[BibT_eX]

[DOI]

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2013

Leader Election and Centers and Medians in Tree Networks.

[BibT_eX]

[DOI]

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2013

Ring Exploration with Oblivious Myopic Robots.

[BibT_eX]

[DOI]

Proceedings of the SAFECOMP 2013, 2013

Ring Exploration by Oblivious Agents with Local Vision.

[BibT_eX]

[DOI]

Proceedings of the IEEE 33rd International Conference on Distributed Computing Systems, 2013

Fast Leader (Full) Recovery Despite Dynamic Faults.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing and Networking, 14th International Conference, 2013

Linear Time Distributed Swap Edge Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 8th International Conference, 2013

2012

Algorithme autostabilisant construisant un petit ensemble k-dominant.

[BibT_eX]

[DOI]

Tech. Sci. Informatiques, 2012

Brief Announcement: Self-stabilizing Silent Disjunction in an Anonymous Network.

[BibT_eX]

[DOI]

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2012

2011

Un algorithme autostabilisant pour le problème du K-partitionnement sur graphe pondéré.

[BibT_eX]

[DOI]

Tech. Sci. Informatiques, 2011

Self-stabilizing leader election in optimal space under an arbitrary scheduler.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

A randomized algorithm for two servers in cross polytope spaces.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

An O(n)-time self-stabilizing leader election algorithm.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 2011

Self-Stabilizing k-out-of-ℓ Exclusion in Tree Networks.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2011

Knowledge State Algorithms.

[BibT_eX]

[DOI]

Algorithmica, 2011

Brief Announcement: A Stable and Robust Membership Protocol.

[BibT_eX]

[DOI]

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2011

Brief Announcement: Sorting on Skip Chains.

[BibT_eX]

[DOI]

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2011

Self-stabilizing Hierarchical Construction of Bounded Size Clusters.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2011

On-Line Optimization of Publish/Subscribe Overlays.

[BibT_eX]

[DOI]

Proceedings of the 25th IEEE International Symposium on Parallel and Distributed Processing, 2011

Multi-resource Allocation with Unknown Participants.

[BibT_eX]

[DOI]

Proceedings of the Second International Conference on Networking and Computing, 2011

Sorting on Skip Chains.

[BibT_eX]

[DOI]

Proceedings of the Second International Conference on Networking and Computing, 2011

2010

A self-stabilizing k-clustering algorithm for weighted graphs.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 2010

A Self-Stabilizing O(k)-Time k-Clustering Algorithm.

[BibT_eX]

[DOI]

Comput. J., 2010

Self-stabilizing Leader Election in Dynamic Networks.

[BibT_eX]

[DOI]

Hema Piniganti

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2010

2009

A quadratic time 2-approximation algorithm for block sorting.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

Optimally competitive list batching.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2009

Knowledge States for the Caching Problem in Shared Memory Multiprocessor Systems.

[BibT_eX]

[DOI]

Rüdiger Reischuk

Int. J. Found. Comput. Sci., 2009

A Program to Determine the Exact Competitive Ratio of List s-Batching with Unit Jobs

[BibT_eX]

[DOI]

CoRR, 2009

A Self-Stabilizing O(n)-Round k-Clustering Algorithm.

[BibT_eX]

[DOI]

Proceedings of the 28th IEEE Symposium on Reliable Distributed Systems (SRDS 2009), 2009

Self-Stabilizing k-out-of-l exclusion on tree networks.

[BibT_eX]

[DOI]

Proceedings of the 23rd IEEE International Symposium on Parallel and Distributed Processing, 2009

A Self-stabilizing K-Clustering Algorithm Using an Arbitrary Metric.

[BibT_eX]

[DOI]

Proceedings of the Euro-Par 2009 Parallel Processing, 2009

2008

Space efficient and time optimal distributed BFS tree construction.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2008

Synchronization Algorithms on Oriented Chains.

[BibT_eX]

[DOI]

Sci. Ann. Comput. Sci., 2008

Self-stabilizing K-out-of-L exclusion on tree network

[BibT_eX]

[DOI]

CoRR, 2008

Self-Stabilizing Leader Election in Optimal Space.

[BibT_eX]

[DOI]

Proceedings of the Stabilization, 2008

Local Synchronization on Oriented Rings.

[BibT_eX]

[DOI]

Proceedings of the Stabilization, 2008

Self-stabilizing algorithms for sorting and heapification.

[BibT_eX]

[DOI]

Proceedings of the 22nd IEEE International Symposium on Parallel and Distributed Processing, 2008

Knowledge States: A Tool for Randomized Online Algorithms.

[BibT_eX]

[DOI]

Rüdiger Reischuk

Proceedings of the 41st Hawaii International International Conference on Systems Science (HICSS-41 2008), 2008

2007

Uniform metrical task systems with a limited number of states.

[BibT_eX]

[DOI]

John Noga

Inf. Process. Lett., 2007

Knowledge State Algorithms: Randomization with Limited Information

[BibT_eX]

[DOI]

Rüdiger Reischuk

CoRR, 2007

Equitable Revisited.

[BibT_eX]

[DOI]

John Noga

Proceedings of the Algorithms, 2007

2006

T-Theory Applications to Online Algorithms for the Server Problem

[BibT_eX]

[DOI]

James A. Oravec

CoRR, 2006

On Self-stabilizing Search Trees.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing, 20th International Symposium, 2006

Self-stabilizing Space Optimal Synchronization Algorithms on Trees.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2006

2005

The algebraic Monge property and path problems.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2005

A Better Algorithm for Uniform Metrical Task Systems with Few States.

[BibT_eX]

[DOI]

John Noga

Proceedings of the 8th International Symposium on Parallel Architectures, 2005

A Faster and Simpler 2-Approximation Algorithm for Block Sorting.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

The Delayed k-Server Problem.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

Optimal Integer Alphabetic Trees in Linear Time.

[BibT_eX]

[DOI]

T. C. Hu

J. David Morgenthaler

Proceedings of the Algorithms, 2005

2004

Work-Efficient Algorithms For The Construction Of Length-Limited Huffman Codes.

[BibT_eX]

[DOI]

Marek Karpinski

Yakov Nekrich

Parallel Process. Lett., 2004

Embedding A Complete Binary Tree Into A Three-Dimensional Grid.

[BibT_eX]

[DOI]

Charles O. Shields Jr.

Ivan Hal Sudborough

J. Interconnect. Networks, 2004

2003

Block Sorting is Hard.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2003

Faster Algorithms for k-Medians in Trees.

[BibT_eX]

[DOI]

Robert Benkoczi

Binay K. Bhattacharya

Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

2002

The 3-server problem in the plane.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2002

Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property.

[BibT_eX]

[DOI]

J. Algorithms, 2002

Fast Algorithms with Algebraic Monge Properties.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

Fixed Layer Embeddings of Binary Trees.

[BibT_eX]

[DOI]

Charles O. Shields Jr.

Ivan Hal Sudborough

Proceedings of the International Symposium on Parallel Architectures, 2002

2001

The k-Median Problem for Directed Trees.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

2000

Trackless online algorithms for the server problem.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2000

Limited bookmark randomized online algorithms for the paging problem.

[BibT_eX]

[DOI]

Rudolf Fleischer

Inf. Process. Lett., 2000

A Randomized Algorithm for Two Servers on the Line.

[BibT_eX]

[DOI]

Yair Bartal

Inf. Comput., 2000

Three-Dimensional Embedding of Binary Trees.

[BibT_eX]

[DOI]

Charles O. Shields Jr.

Ivan Hal Sudborough

Proceedings of the 5th International Symposium on Parallel Architectures, 2000

1998

Almost Optimal Sublinear Time Parallel Recognition Algorithms for Three Subclasses of Context Free Languages.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1998

The Optimal Alphabetic Tree Problem Revisited.

[BibT_eX]

[DOI]

J. Algorithms, 1998

A Randomized Algorithm for Two Servers on the Line (Extended Abstract).

[BibT_eX]

[DOI]

Yair Bartal

Proceedings of the Algorithms, 1998

1997

Correctness of Constructing Optimal Alphabetic Trees Revisited.

[BibT_eX]

[DOI]

Marek Karpinski

Theor. Comput. Sci., 1997

Page Migration Algorithms Using Work Functions.

[BibT_eX]

[DOI]

J. Algorithms, 1997

A Better Lower Bound on the Competitive Ratio of the Randomized 2-Server Problem.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1997

1996

A Parallel Algorithm for Optimum Height-Limited Alphabetic Binary Trees.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 1996

Sequential and Parallel Subquadratic Work Algorithms for Constructing Approximately Optimal Binary Search Trees.

[BibT_eX]

[DOI]

Marek Karpinski

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Metrical Task Systems, the Server Problem and the Work Function Algorithm.

[BibT_eX]

[DOI]

Proceedings of the Online Algorithms, 1996

1995

Constructing Huffman Trees in Parallel.

[BibT_eX]

[DOI]

SIAM J. Comput., 1995

1994

A Fast Algorithm for Optimum Height-Limited Alphabetic Binary Trees.

[BibT_eX]

[DOI]

SIAM J. Comput., 1994

Generosity Helps or an 11-Competitive Algorithm for Three Servers.

[BibT_eX]

[DOI]

J. Algorithms, 1994

An Optimal Sublinear Time Parallel Algorithm for Some Dynamic Programming Problems.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1994

1993

Parallel Construction of Optimal Alphabetic Trees.

[BibT_eX]

[DOI]

Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

1992

Harmonic is 3-Competitive for Two Servers.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1992

Layout placement for sliced architecture.

[BibT_eX]

[DOI]

Daniel D. Gajski

Allen C.-H. Wu

IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 1992

The Traveler's Problem.

[BibT_eX]

[DOI]

J. Algorithms, 1992

Efficient Sublinear Time Parallel Algorithms for Dynamic Programming and Context-Free Recognition.

[BibT_eX]

[DOI]

Proceedings of the STACS 92, 1992

1991

A New Approach to the Server Problem.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 1991

An Optimal On-Line Algorithm for k-Servers on Trees.

[BibT_eX]

[DOI]

SIAM J. Comput., 1991

On-line Dynamic Programming with Applications to the Prediction of RNA Secondary Structure.

[BibT_eX]

[DOI]

Baruch Schieber

J. Algorithms, 1991

On Fast Algorithms for Two Servers.

[BibT_eX]

[DOI]

J. Algorithms, 1991

A Note on the Server Problem and a Benevolent Adversary.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1991

Parallel Construction of Trees with Optimal Weighted Path Length.

[BibT_eX]

[DOI]

Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, 1991

The Server Problem and On-Line Games.

[BibT_eX]

[DOI]

Proceedings of the On-Line Algorithms, 1991

1990

A Fast Algorithm for Optimal Length-Limited Huffman Codes

[BibT_eX]

[DOI]

J. ACM, July, 1990

Efficient Parallel Algorithms for String Editing and Related Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 1990

An Optimal Algorithm with Unknown Time Complexity for Convex Matrix Searching.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1990

Length-Limited Coding.

[BibT_eX]

[DOI]

Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

1989

Minimum Delay Codes.

[BibT_eX]

[DOI]

SIAM J. Comput., 1989

The Set-Set LCS Problem.

[BibT_eX]

[DOI]

Algorithmica, 1989

Constructing Trees in Parallel.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, 1989

1988

Construction of Optimal Binary Split Trees in the Presence of Bounded Access Probabilities.

[BibT_eX]

[DOI]

James H. Hester

J. Algorithms, 1988

1987

Height Restricted Optimal Binary Trees.

[BibT_eX]

[DOI]

SIAM J. Comput., 1987

The Least Weight Subsequence Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 1987

A Subquadratic Algorithm for Constructing Approximately Optimal Binary Search Trees.

[BibT_eX]

[DOI]

J. Algorithms, 1987

New applications of failure functions.

[BibT_eX]

[DOI]

J. ACM, 1987

Packing Items from a Triangular Distribution.

[BibT_eX]

[DOI]

Kadri Krause

Dennis J. Volper

Inf. Process. Lett., 1987

The Set LCS Problem.

[BibT_eX]

[DOI]

Algorithmica, 1987

1986

Average Case Analysis of Marking Algorithms.

[BibT_eX]

[DOI]

SIAM J. Comput., 1986

1985

Efficient Optimal Pagination of Scrolls.

[BibT_eX]

[DOI]

Commun. ACM, 1985

The Least Weight Subsequence Problem (Extended Abstract)

[BibT_eX]

[DOI]