Reorder Detecting TCP (RD-TCP) with Explicit Packet Drop Notification (EPDN) (2008)
Arjuna Sathiaseelan, Tomasz Radzik
Abstract — Numerous studies have shown that packet reordering is common, especially in networks where there is high degree of parallelism and different link speeds. Reordering of packets decreases...
Implementations of Dynamic Tree Collections Based on Splay Trees (2007)
We describe implementations of two closely related variants of dynamic rooted trees. These variants are similar to Sleator and Tarjan's dynamic trees, but instead of the operation of finding the...
Implementations of Dynamic Tree Collections Based on Splay Trees (2007)
We describe implementations of two closely related variants of dynamic rooted trees. These variants are similar to Sleator and Tarjan's dynamic trees, but instead of the operation of finding the...
Experimental evaluation of algorithmic solutions for the maximum generalised (2007)
Tomasz Radzik, Shengxiang Yang
network ow problem
Approximation bounds for Black Hole Search problems (2007)
Klasing, Ralf, Markou, Euripides, Radzik, Tomasz, Sarracco, Fabiano
A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is the task of...
Approximation bounds for Black Hole Search problems (2007)
Klasing, Ralf, Markou, Euripides, Radzik, Tomasz, Sarracco, Fabiano
A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is the task of...
Approximation bounds for Black Hole Search problems (2007)
Klasing, Ralf, Markou, Euripides, Radzik, Tomasz, Sarracco, Fabiano
A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is the task of...
Approximation bounds for Black Hole Search problems (2007)
Klasing, Ralf, Markou, Euripides, Radzik, Tomasz, Sarracco, Fabiano
A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is the task of...
Hardness and Approximation Results for Black Hole Search in Arbitrary Networks (2006)
Klasing, Ralf, Markou, Euripides, Radzik, Tomasz, Saracco, Fabiano
A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is the task of...
Hardness and Approximation Results for Black Hole Search in Arbitrary Networks (2006)
Klasing, Ralf, Markou, Euripides, Radzik, Tomasz, Saracco, Fabiano
A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is the task of...
Searching for Black-Hole Faults in a Network Using Multiple Agents (2006)
Abstract. We consider a fixed communication network where (software) agents can move freely from node to node along the edges. A black hole is a faulty or malicious node in the network such that if...
Hardness and Approximation Results for Black Hole Search in Arbitrary Networks (2005)
Klasing, Ralf, Markou, Euripides, Radzik, Tomasz, Sarracco, Fabiano
A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is the task of...
Hardness and approximation results for black hole search in arbitrary graphs (2005)
Ralf Klasing, Euripides Markou, Tomasz Radzik, Fabiano Sarracco
Abstract. A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node, without leaving any trace. We consider the task of...
On the wake-up problem in radio networks (2005)
Bogdan S. Chlebus, Leszek Gasieniec, Dariusz R. Kowalski, Tomasz Radzik
Abstract. Radio networks model wireless communication when processing units communicate using one wave frequency. This is captured by the property that multiple messages arriving simultaneously to a...
Approximation bounds for Black Hole Search problems (2005)
Ralf Klasing, Euripides Markou, Tomasz Radzik, Fabiano Sarracco
Abstract. A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is...
Hardness and approximation results for black hole search in arbitrary graphs (2005)
Ralf Klasing, Euripides Markou, Tomasz Radzik, Fabiano Sarracco
Abstract. A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is...
A randomized algorithm for the joining protocol in dynamic distributed networks (2005)
Colin Cooper, Ralf Klasing, Tomasz Radzik
We describe a randomized algorithm for assigning neighbours to vertices joining a dynamic distributed network. The aim of the algorithm is to maintain connectivity, low diameter and constant vertex...
A randomized algorithm for the joining protocol in dynamic distributed networks (2004)
Cooper, Colin, Klasing, Ralf, Radzik, Tomasz
We consider a randomized algorithm for assigning neighbours to vertices joining a dynamic distributed network. The algorithm acts to maintain connectivity, low diameter and constant vertex degree....
A randomized algorithm for the joining protocol in dynamic distributed networks (2004)
Cooper, Colin, Klasing, Ralf, Radzik, Tomasz
We consider a randomized algorithm for assigning neighbours to vertices joining a dynamic distributed network. The algorithm acts to maintain connectivity, low diameter and constant vertex degree....
A randomized algorithm for the joining protocol in dynamic distributed networks (2004)
Cooper, Colin, Klasing, Ralf, Radzik, Tomasz
We consider a randomized algorithm for assigning neighbours to vertices joining a dynamic distributed network. The algorithm acts to maintain connectivity, low diameter and constant vertex degree....
Classroom Examples of Robustness Problems in Geometric Computations (2004)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee, Albers, Susanne, ...
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations...
Flows on Few Paths: Algorithms and Lower Bounds (2004)
Martens, Maren, Skutella, Martin, Albers, Susanne, Radzik, Tomasz
In classical network flow theory, flow being sent from a source to a destination may be split into a large number of chunks traveling on different paths through the network. This effect is undesired...
Super Scalar Sample Sort (2004)
Sanders, Peter, Albers, Susanne, Radzik, Tomasz
Sample sort, a generalization of quicksort that partitions the input into many pieces, is known as the best practical comparison based sorting algorithm for distributed memory parallel computers. We...
Incremental Algorithms for Facility Location and k-Median (2004)
Fotakis, Dimitris, Albers, Susanne, Radzik, Tomasz
In the incremental versions of Facility Location and k-Median, the demand points arrive one at a time and the algorithm must maintain a good solution by either adding each new demand to an existing...
Boros, Endre, Elbassioni, Khaled, Gurvich, Vladimir, Albers, Susanne, Radzik, Tomasz
A minimal blocker in a bipartite graph $G$ is a minimal set of edges the removal of which leaves no perfect matching in $G$. We give an explicit characterization of the minimal blockers of a...
Improving the Performance of TCP in the Case of Packet Reordering (2004)
Arjuna Sathiaseelan, Tomasz Radzik
Abstract. Numerous studies have shown that packet reordering is common, especially in high speed networks where there is high degree of parallelism and different link speeds. Reordering of packets...
Deterministic Communication in Radio Networks with Large Labels? (2004)
Leszek G, Aris Pagourtzis, Igor Potapov, Tomasz Radzik
- a communication procedure which gives an O(n3/2 log3 n)-time deterministic gossiping algorithm for directed networks and an O(n4/3 log3 n)-time algorithm for undirected networks; and- a gossiping...
Boros, Endre, Elbassioni, Khaled, Gurvich, Vladimir, Albers, Susanne, Radzik, Tomasz
A minimal blocker in a bipartite graph $G$ is a minimal set of edges the removal of which leaves no perfect matching in $G$. We give an explicit characterization of the minimal blockers of a...
Incremental Algorithms for Facility Location and k-Median (2004)
Fotakis, Dimitris, Albers, Susanne, Radzik, Tomasz
In the incremental versions of Facility Location and k-Median, the demand points arrive one at a time and the algorithm must maintain a good solution by either adding each new demand to an existing...
Classroom Examples of Robustness Problems in Geometric Computations (2004)
Kettner, Lutz, Mehlhorn, Kurt, Pion, Sylvain, Schirra, Stefan, Yap, Chee, Albers, Susanne, ...
The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations...
Flows on Few Paths: Algorithms and Lower Bounds (2004)
Martens, Maren, Skutella, Martin, Albers, Susanne, Radzik, Tomasz
In classical network flow theory, flow being sent from a source to a destination may be split into a large number of chunks traveling on different paths through the network. This effect is undesired...
Super Scalar Sample Sort (2004)
Sanders, Peter, Albers, Susanne, Radzik, Tomasz
Sample sort, a generalization of quicksort that partitions the input into many pieces, is known as the best practical comparison based sorting algorithm for distributed memory parallel computers. We...
Solving the biobjective minimum spanning tree problem using a k-best algorithm (2003)
Abstract. We consider a two-phase method for computing the complete set of efficient solutions of the biobjective minimum spanning tree problem. The first phase computes the extreme efficient...
Using remote memory paging for handheld devices in a pervasive computing environment (2003)
Arjuna Sathiaseelan, Tomasz Radzik
Abstract. Pervasive computing is the technology for the future. With efficient smart spaces and the proliferation of mobile devices and wireless networking standards, there are a lot of interesting...
RD-TCP: Reorder Detecting TCP (2003)
Arjuna Sathiaseelan, Tomasz Radzik
Abstract. Numerous studies have shown that packet reordering is common, especially in high speed networks where there is high degree of parallelism and different link speeds. Reordering of packets...
RD-TCP: Reorder Detecting TCP (2003)
Arjuna Sathiaseelan, Arjuna Sathiaseelan, Tomasz Radzik, Tomasz Radzik
Numerous studies have shown that packet reordering is common, especially in networks with a high degree of parallelism. Reordering of packets decreases the TCP performance of a network, mainly...
Implementation of Dynamic Trees with In-Subtree Operations (1998)
We describe an implementation of dynamic trees with \in-subtree" operations. Our implementation follows Sleator and Tarjan's framework of dynamic-tree implementations based on splay trees....
A Heuristic Improvement of the Bellman-Ford Algorithm, (1997)
Goldberg, Andrew, Radzik, Tomasz
We describe a new shortest paths algorithm. Our algorithm achieves the same O(nm) worst-case time bound as Bellman-Ford algorithm but is superior in practice.
Shortest Paths Algorithms: Theory And Experimental Evaluation (1993)
Boris Cherkassky, Andrew V. Goldberg, Tomasz Radzik
. We conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. We also suggest new algorithms motivated by the experimental results and prove...
A Heuristic Improvement Of The Bellman-Ford Algorithm (1993)
Andrew V. Goldberg, Tomasz Radzik
. We describe a new shortest paths algorithm. Our algorithm achieves the same O(nm) worst-case time bound as Bellman-Ford algorithm but is superior in practice. 1. Introduction The Bellman-Ford...
Shortest Paths Algorithms: Theory And Experimental Evaluation (1993)
Boris V. Cherkassky, Andrew V. Goldberg, Tomasz Radzik
. We conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. We also suggest new algorithms motivated by the experimental results and prove...