G. De Marco, A. Pelc,
Deterministic broadcasting time with partial knowledge of the network,
*Theoretical Computer Science* 290 (2003), 2009-2020.

Preliminary version appeared in:

Proc. 11th Annual International Symposium on Algorithms And Computation (ISAAC 2000), Taipei, Taiwan, December 2000, LNCS 1969, 374-385.

Abstract:

We consider the time of deterministic broadcasting in networks whose nodes
have limited knowledge of network topology. Each node *v*
knows only the part of the network within *knowledge radius*
*r* from it, i.e.,
it knows the graph induced by all nodes at distance at most
*r* from *v*. Apart from that, each node knows the maximum
degree *D* of the
network.
One node of the network, called the *source*, has a message
which has to reach all other nodes. We adopt the widely studied communication
model called the *one-way* model in which, in every round,
each node can communicate with at most one neighbor, and in each pair of
nodes communicating in a given round, one can only send a message
while the other can only receive it.
This is the weakest of all store-and-forward models for
point-to-point networks, and hence our algorithms
work for other models as well, in at most the same time.
We show trade-offs between knowledge radius and time of
deterministic broadcasting, when the
knowledge radius is small, i.e., when nodes are only aware of their close
vicinity. While for
knowledge radius 0, minimum broadcasting time is *Theta (e)*, where
*e* is the number of edges in the network, broadcasting can be usually
completed faster for positive knowledge radius. Our main results concern
knowledge radius 1.
We develop fast broadcasting algorithms and analyze their
execution time. We also prove lower bounds on broadcasting time, showing that
our algorithms are close to optimal.

A. Dessmark, A. Lingas, A. Pelc,
Tradeoffs between load and degree in virtual path layouts,
*Parallel Processing Letters* 13 (2003), 485-496.

Abstract:

We study virtual path layouts in ATM networks.
Packets are routed along virtual paths in the network by maintaining
a routing field whose subfields determine
intermediate destinations of the packet, i.e., the endpoints of virtual paths
on its way to the final destination.
Most of the research on virtual path layouts has focused on tradeoffs between
*load* (i.e., the maximum number of virtual paths passing
through a link) and the *hop number* of the layout
(i.e., the maximum number of virtual paths needed to travel between any two nodes).
There is however another
important limitation on construction of layouts, resulting from technological
properties of switches situated at nodes. This bound is the *degree*
of the layout
(i.e., the maximum number of virtual paths
with a common endpoint). In this paper we study relations between these
three parameters of virtual path layouts, for the all-to-all problem.
For any integer *h*, we show tradeoffs
between load and degree of *h*-hop layouts in the ring and in
the mesh by establishing upper and lower bounds on these parameters.
Our bounds on the degree of an *h*-hop layout
of given load are asymptotically tight and the bounds on the load
of an *h*-hop layout of given degree are asymptotically tight for constant *h*.

J. Czyzowicz, W. Fraczak, A. Pelc, W. Rytter,
Linear time prime decomposition of regular prefix codes,
*International Journal of Foundations of Computer Science* 14 (2003), 1019-1031.

Preliminary version appeared as:

J. Czyzowicz, W. Fraczak, A. Pelc, W. Rytter, Prime decompositions of regular prefix codes, Proc. 7th International Conference on Implementation and Application of Automata (CIAA'2002), July 2002, Tours, France, LNCS 2608, 85-94.

Abstract:

One of the new approaches to data classification uses prefix codes
and finite state automata as representations of prefix codes. A
prefix code is a (possibly infinite) set of strings such that no
string is a prefix of another one. An important task driven by the
need for the efficient storage of such automata in memory is the
decomposition (in the sense of formal languages concatenation) of
prefix codes into prime factors. We investigate properties of such
prefix code decompositions. A prime decomposition is a
decomposition of a prefix code into a concatenation of nontrivial
prime prefix codes. A prefix code is prime if it cannot be
decomposed into at least two nontrivial prefix codes. In the paper a
linear time algorithm is designed which finds the prime
decomposition *F_1F_2 ... F_k* of a regular prefix code *F* given
by its minimal deterministic automaton. Our results are especially
interesting for infinite regular prefix codes.

J.Czyzowicz, E.Kranakis, D. Krizanc, M.V.Martin, A. Pelc,
Enhancing hyperlink structure for improving Web performance,
*Journal of Web Engineering* 1 (2003), 93-127.

Abstract:

In a Web site, each page *v* has a certain probability *p(v)*
of being requested by a user. The access cost of a Web site is the sum of
*p(v)c(r,v)*, over all pages *v*, where *c(r,v)* is the cost of the
shortest path between the home page *r* and page *v*.
This research concerns the problem of minimizing the access cost of a Web site
by adding hotlinks over its underlying structure.
We propose an improvement of Web site access by making the most
popular pages more accessible to the users. We present heuristic algorithms for the
hotlink assignment problem. These algorithms are tested and compared
by simulation on real and random Web sites. We develop the Hotlink Optimizer (HotOpt),
a new software tool that finds an assignment of hotlinks reducing the access cost
of a Web site. HotOpt is empowered by one of the algorithms presented in the paper.

B.S.Chlebus, L.Gasieniec, A. Pelc,
Deterministic computations on a PRAM with static processor and memory faults,
*Fundamenta Informaticae* 55 (2003), 285-306.

Preliminary version appeared as:

B.S.Chlebus, L.Gasieniec, A. Pelc, Fast deterministic simulation of computations on faulty parallel machines, Proc. Third Annual European Symposium on Algorithms ESA'95, Corfu, Greece, September 1995, LNCS 979, p. 89-101.

Abstract:

We consider Parallel Random Access Machine (PRAM) which has some
processors and memory cells faulty.
The faults considered are static, i.e., once the machine starts to operate,
the operational/faulty status of PRAM components does not change.
We develop a deterministic simulation of a fully operational PRAM
on a similar faulty machine which has constant fractions of
faults among processors and memory cells.
The simulating PRAM has *n* processors and *m* memory cells,
and simulates a PRAM with *n* processors and a constant
fraction of *m* memory cells.
The simulation is in two phases: it starts with preprocessing, which is
followed by the simulation proper performed in a step-by-step fashion.
Preprocessing is performed in time *O((m/n+ log n)log n)*.
The slowdown of a step-by-step part of the simulation is *O(log m)*.