Tomasz Radzik

Nobutaka Shimizu

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

2024

Perpetual maintenance of machines with different urgency requirements.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., February, 2024

New bounds for single-machine time-dependent scheduling with uniform deterioration.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2024

Discrete Incremental Voting on Expanders.

[BibT_eX]

[DOI]

CoRR, 2024

A Simple Model of Influence: Details and Variants of Dynamics.

[BibT_eX]

[DOI]

Proceedings of the Modelling and Mining Networks - 19th International Workshop, 2024

2023

New Bounds for Time-Dependent Scheduling with Uniform Deterioration.

[BibT_eX]

[DOI]

CoRR, 2023

A Simple Model of Influence.

[BibT_eX]

[DOI]

Nan Kang

Proceedings of the Algorithms and Models for the Web Graph - 18th International Workshop, 2023

Brief Announcement: Discrete Incremental Voting.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, 2023

Distributed Averaging in Opinion Dynamics.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, 2023

Discrete Incremental Voting.

[BibT_eX]

[DOI]

Proceedings of the 27th International Conference on Principles of Distributed Systems, 2023

2022

Distributed Averaging in Population Protocols.

[BibT_eX]

[DOI]

Nicolás Rivera

CoRR, 2022

Perpetual maintenance of machines with different urgency requirements.

[BibT_eX]

[DOI]

CoRR, 2022

Selected Papers of the 31st International Workshop on Combinatorial Algorithms, IWOCA 2020.

[BibT_eX]

[DOI]

Leszek Gasieniec

Algorithmica, 2022

On early extinction and the effect of travelling in the SIR model.

[BibT_eX]

[DOI]

Proceedings of the Uncertainty in Artificial Intelligence, 2022

2021

Time-space trade-offs in population protocols for the majority problem.

[BibT_eX]

[DOI]

Distributed Comput., 2021

Servicing Timed Requests on a Line.

[BibT_eX]

[DOI]

Angelos Gkikas

CoRR, 2021

2020

IWOCA 2020 in Bordeaux (Oops! On-Line!).

[BibT_eX]

[DOI]

Bull. EATCS, 2020

2019

New Cover Time Bounds for the Coalescing-Branching Random Walk on Graphs.

[BibT_eX]

[DOI]

ACM Trans. Parallel Comput., 2019

On Counting the Population Size.

[BibT_eX]

[DOI]

Petra Berenbrink

Dominik Kaaser

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Fair Hitting Sequence Problem: Scheduling Activities with Varied Frequency Requirements.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity - 11th International Conference, 2019

2018

Dispersion processes.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2018

Recent Results in Population Protocols for Exact Majority and Leader Election.

[BibT_eX]

[DOI]

Robert Elsässer

Bull. EATCS, 2018

A population protocol for exact majority with O(\log5/3n) stabilization time and asymptotically optimal number of states.

[BibT_eX]

[DOI]

CoRR, 2018

Majority & Stabilization in Population Protocols.

[BibT_eX]

[DOI]

CoRR, 2018

A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Distributed Computing, 2018

Tight Bounds for Deterministic h-Shot Broadcast in Ad-Hoc Directed Radio Networks.

[BibT_eX]

[DOI]

Aris Pagourtzis

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

2017

Population protocols for leader election and exact majority with O(log^2 n) states and O(log^2 n) convergence time.

[BibT_eX]

[DOI]

CoRR, 2017

Robustness of the Rotor-Router Mechanism.

[BibT_eX]

[DOI]

Algorithmica, 2017

Fast Plurality Consensus in Regular Expanders.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Distributed Computing, 2017

Improved Cover Time Bounds for the Coalescing-Branching Random Walk on Graphs.

[BibT_eX]

[DOI]

Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, 2017

Bamboo Garden Trimming Problem (Perpetual Maintenance of Machines with Different Attendance Urgency Factors).

[BibT_eX]

[DOI]

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

Brief Announcement: Population Protocols for Leader Election and Exact Majority with O(log2 n) States and O(log2 n) Convergence Time.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

2016

2015 London Stringology Days and London Algorithmic Workshop (LSD & LAW).

[BibT_eX]

[DOI]

Jakub Radoszewski

J. Discrete Algorithms, 2016

Fast Low-Cost Estimation of Network Properties Using Random Walks.

[BibT_eX]

[DOI]

Internet Math., 2016

Detection of known and unknown DDoS attacks using Artificial Neural Networks.

[BibT_eX]

[DOI]

Alan Saied

Richard E. Overill

Neurocomputing, 2016

The Coalescing-Branching Random Walk on Expanders and the Dual Epidemic Process.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

2015

Fast Consensus for Voting on General Expander Graphs.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 29th International Symposium, 2015

Coalescing Walks on Rotor-Router Systems.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2015

2014

Estimating network parameters using random walks.

[BibT_eX]

[DOI]

Soc. Netw. Anal. Min., 2014

A Fast Algorithm to Find All High-Degree Vertices in Graphs with a Power-Law Degree Sequence.

[BibT_eX]

[DOI]

Internet Math., 2014

Random walks in recommender systems: exact computation and simulations.

[BibT_eX]

[DOI]

Proceedings of the 23rd International World Wide Web Conference, 2014

Artificial Neural Networks in the Detection of Known and Unknown DDoS Attacks: Proof-of-Concept.

[BibT_eX]

[DOI]

Alan Saied

Richard E. Overill

Proceedings of the Highlights of Practical Applications of Heterogeneous Multi-Agent Systems. The PAAMS Collection, 2014

The Power of Two Choices in Distributed Voting.

[BibT_eX]

[DOI]

Robert Elsässer

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

The cover times of random walks on random uniform hypergraphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Coalescing Random Walks and Voting on Connected Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2013

Approximation Bounds on the Number of Mixedcast Rounds in Wireless Ad-Hoc Networks.

[BibT_eX]

[DOI]

Sang-Hyuk Lee

Proceedings of the Combinatorial Algorithms - 24th International Workshop, 2013

2012

Editorial.

[BibT_eX]

[DOI]

German Tischler

J. Discrete Algorithms, 2012

Testing connectivity of faulty networks in sublinear time.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2012

A fast algorithm to find all high degree vertices in power law graphs.

[BibT_eX]

[DOI]

Proceedings of the 21st World Wide Web Conference, 2012

Coalescing random walks and voting on graphs.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012

Improved Approximation Bounds for Maximum Lifetime Problems in Wireless Ad-Hoc Network.

[BibT_eX]

[DOI]

Sang-Hyuk Lee

Proceedings of the Ad-hoc, Mobile, and Wireless Networks - 11th International Conference, 2012

2011

Tree exploration with logarithmic memory.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2011

The Cover Times of Random Walks on Hypergraphs.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2011

2010

Locating and repairing faults in a network with mobile agents.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

Speeding Up Random Walks with Neighborhood Exploration.

[BibT_eX]

[DOI]

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

Efficient Connectivity Testing of Hypercubic Networks with Faults.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 21st International Workshop, 2010

The Cover Time of Cartesian Product Graphs.

[BibT_eX]

[DOI]

Mohammed Amin Abdullah

Proceedings of the Combinatorial Algorithms - 21st International Workshop, 2010

Time-Efficient Broadcast in Radio Networks.

[BibT_eX]

[DOI]

David Peleg

Proceedings of the Graphs and Algorithms in Communication Networks: Studies in Broadband, 2010

2009

Fractional Combinatorial Optimization.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Optimization, Second Edition, 2009

Multiple Random Walks in Random Regular Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2009

Many-to-Many Communication in Radio Networks.

[BibT_eX]

[DOI]

Bogdan S. Chlebus

Dariusz R. Kowalski

Algorithmica, 2009

Robustness of the Rotor-router Mechanism.

[BibT_eX]

[DOI]

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

Multiple Random Walks and Interacting Particle Systems.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009

2008

A randomized algorithm for the joining protocol in dynamic distributed networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2008

Approximation bounds for Black Hole Search problems.

[BibT_eX]

[DOI]

Networks, 2008

Computing all efficient solutions of the biobjective minimum spanning tree problem.

[BibT_eX]

[DOI]

Sarah Steiner

Comput. Oper. Res., 2008

Memory Efficient Anonymous Graph Exploration.

[BibT_eX]

[DOI]

Leszek Gasieniec

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2008

2007

Hardness and approximation results for Black Hole Search in arbitrary networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

Deterministic Communication in Radio Networks with Large Labels.

[BibT_eX]

[DOI]

Algorithmica, 2007

Tree exploration with logarithmic memory.

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2006

Guest Editor's Foreword.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2006

Reorder notifying TCP (RN-TCP) with explicit packet drop notification (EPDN).

[BibT_eX]

[DOI]

Int. J. Commun. Syst., 2006

Foreword.

[BibT_eX]

[DOI]

Susanne Albers

Algorithmica, 2006

Searching for Black-Hole Faults in a Network Using Multiple Agents.

[BibT_eX]

[DOI]

Proceedings of the Principles of Distributed Systems, 10th International Conference, 2006

On Many-to-Many Communication in Packet Radio Networks.

[BibT_eX]

[DOI]

Bogdan S. Chlebus

Dariusz R. Kowalski

Proceedings of the Principles of Distributed Systems, 10th International Conference, 2006

2005

Hardness and Approximation Results for Black Hole Search in Arbitrary Graphs.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2005

Heuristic Enhancements to the k-best Method for Solving Biobjective Combinatorial Optimisation Problems.

[BibT_eX]

[DOI]

Sarah Steiner

Proceedings of the Operations Research Proceedings 2005, 2005

Robust TCP (TCP-R) with Explicit Packet Drop Notification (EPDN) for Satellite Networks.

[BibT_eX]

[DOI]

Proceedings of the Networking, 2005

On the Wake-Up Problem in Radio Networks.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004

Improving time bounds on maximum generalised flow computations by contracting the network.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

Faster Deterministic Gossiping in Directed Ad Hoc Radio Networks.

[BibT_eX]

[DOI]

Leszek Gasieniec

Qin Xin

Proceedings of the Algorithm Theory, 2004

Improving the Performance of TCP in the Case of Packet Reordering.

[BibT_eX]

[DOI]

Proceedings of the High Speed Networks and Multimedia Communications, 2004

2003

RD-TCP: Reorder Detecting TCP.

[BibT_eX]

[DOI]

Proceedings of the High Speed Networks and Multimedia Communications, 2003

1998

Faster Algorithms for the Generalized Network Flow Problem.

[BibT_eX]

[DOI]

Math. Oper. Res., 1998

Implementation of Dynamic Trees with In-Subtree Operations.

[BibT_eX]

[DOI]

ACM J. Exp. Algorithmics, 1998

1997

Fast deterministic approximation for the multicommodity flow problem.

[BibT_eX]

[DOI]

Math. Program., 1997

Implementations of Dynamic Tree Collections Based on Splay Trees.

[BibT_eX]

Proceedings of the Workshop on Algorithm Engineering, 1997

1996

Shortest paths algorithms: Theory and experimental evaluation.

[BibT_eX]

[DOI]

Boris V. Cherkassky

Andrew V. Goldberg

Math. Program., 1996

1994

Tight Bounds on the Number of Minimum-Mean Cycle Cancellations and Related Results.

[BibT_eX]

[DOI]

Andrew V. Goldberg

Algorithmica, 1994

1992

Algorithms for some linear and fractional combinatorial optimization problems.

[BibT_eX]

[DOI]

PhD thesis, 1992

Minimizing Capacity Violations in a Transshipment Network.

[BibT_eX]

[DOI]

Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

Newton's Method for Fractional Combinatorial Optimization

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991

Improved Deterministic Parallel Integer Sorting

[BibT_eX]

[DOI]

Inf. Comput., September, 1991

Connectivity vs. Reachability

[BibT_eX]

[DOI]

Marek Chrobak

Howard J. Karloff

Inf. Comput., April, 1991

1990

Every Robust CRCW PRAM Can Efficiently Simulate a PRIORITY PRAM.

[BibT_eX]

[DOI]

Torben Hagerup

Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 1990

1989

New Simulations between CRCW PRAMs.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 1989

1988

Testing Isomorphism of Outerplanar Graphs in Parallel.

[BibT_eX]

[DOI]

Bogdan S. Chlebus

Krzysztof Diks