P. Panaite, A. Pelc,
Exploring unknown undirected graphs,
*Journal of Algorithms* 33 (1999), 281-295.

Preliminary version appeared in: Proc. 9th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA'98), San Francisco, USA, January 1998, pp. 316-322.

Abstract:

A robot has to construct a complete map of an unknown environment modeled as
an undirected connected graph. The task is to explore all nodes and edges of
the graph using the minimum number of edge traversals. The *penalty* of
an exploration algorithm running on a graph *G=(V(G),E(G))* is
the worst-case number
of traversals in excess of the lower bound *|E(G)|* that it must
perform in order
to explore the entire graph. We give an exploration algorithm whose penalty
is *O(|V(G)|)* for every graph. We also show that some natural
exploration algorithms cannot achieve this efficiency.

K. Diks, A. Lingas, A. Pelc,
An optimal algorithm for
broadcasting multiple messages in trees,
*Journal of Parallel and Distributed Computing* 59 (1999), 465-474.

Preliminary version appeared as:

K. Diks, A. Lingas, A. Pelc, Broadcasting multiple messages in trees, Proc. 4th Coll. on Structural Information and Communication Complexity, SIROCCO'97, Ascona, Switzerland, July 1997, 69-80.

Abstract:

We consider multiple message broadcasting in tree networks. The source
(considered as the root of the tree) has
*k* messages which have to be broadcast to all nodes of the tree. In every time
unit each node can send one of already obtained messages to one of its
children. A *k*-message broadcasting scheme prescribes in which
time unit a given node
should send a message to which child.
It is *k*-optimal if it achieves the smallest
possible time for broadcasting *k* messages from the source to all nodes.
We give an algorithm to construct
a *k*-optimal broadcasting scheme for an arbitrary *n*-node tree.
The time complexity of our algorithm is *O(nk)*, i.e., the best possible.

E. Kranakis, A. Pelc, A. Spatharis,
Optimal adaptive fault diagnosis for simple multiprocessor systems,
*Networks* 34 (1999), 206-214.

Preliminary version appeared in:

Proc. 5th Int. Coll. on Structural Information and Communication Complexity, SIROCCO'98, Amalfi, Italy, June 1998, 82-97.

Abstract:

We study *adaptive system-level fault diagnosis* for multiprocessor systems. Processors can test each other and future tests can be selected on the basis of previous test results. Fault-free testers give always correct test results,
while faulty testers are completely unreliable.
The aim of diagnosis is to determine correctly the fault status of all processors. We present adaptive diagnosis algorithms for systems modeled by trees, rings and tori.
These algorithms use the smallest possible number of tests in each case.
Our results also
imply optimal diagnosis for more general systems, assuming a small
number of faults. The cost of adaptive diagnosis turns out to be
significantly smaller than that of classical (* one-step*) diagnosis.

L. Gasieniec, E. Kranakis, D. Krizanc, A. Pelc,
Minimizing congestion of layouts for ATM networks with faulty links,
*International Journal of Foundations of Computer Science* 10 (1999), 503-512.

Preliminary version appeared in:

Proc. 21st International Symposium on Mathematical Foundations of Computer Science MFCS'96, Cracow, Poland, September 1996, LNCS 1113, pp.372-381.

Abstract:

We consider the problem of constructing virtual path layouts for an
ATM network consisting of a complete network K of *n* processors
in which a certain number of links may fail.
Our main goal is to construct layouts which tolerate any configuration of up to
*f* faults and have the least possible congestion.
First, we study the minimal congestion of 1-hop *f*-tolerant layouts
in K. For any positive integer *f* we give upper and lower bounds
on this minimal congestion and construct *f*-tolerant layouts
with congestion corresponding to the upper bounds.
Our results are based on a precise analysis of
the diameter of the network which results from K by deleting
links from a set of bounded size.
Next we study the minimal congestion of *h*-hop *f*-tolerant layouts
in K, for larger values of the number *h* of hops. We give upper and
lower bounds on the order of magnitude of this congestion, based on results for
1-hop layouts.
Finally, we consider a random, rather than worst case, fault distribution where
links fail independently with constant probability *p<1*.
Our goal now is to construct layouts with low congestion that
tolerate the existing faults with high probability.
For any *p<1*, we show the existence of 1-hop layouts
in K, with congestion O(log *n*).