Andrzej Pelc

Andrzej Pelc

Auto-generated profile, based on publicly available information

Andrzej Pelc

Département d’informatique, Université du Québec en Outaouais, Gatineau, Canada

Research Focus & Metrics

Academic Career Length

34Years (1993-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
19 June 2006 in Algorithmica
Verified
Journal Article
Closed access
PDF file
ADAnders Dessmark
Anders Dessmark
PFPierre Fraigniaud
Pierre Fraigniaud
DKDariusz R. Kowalski
Dariusz R. Kowalski
APAndrzej Pelc
Andrzej Pelc

23 January 2012 in Networks
Verified
Journal Article
Closed access
PDF file
APAndrzej Pelc
Andrzej Pelc

14 January 2010 in Theoretical Computer Science
Verified
Journal Article
Closed access
PDF file
PFPaola Flocchini
Paola Flocchini
DIDavid Ilcinkas
David Ilcinkas
APAndrzej Pelc
Andrzej Pelc
NSNicola Santoro
Nicola Santoro

1 January 2007 in Combinatorics, Probability and Computing
Verified
Journal Article
Closed access
PDF file
JCJurek Czyzowicz
Jurek Czyzowicz
DKDariusz Kowalski
Dariusz Kowalski
EMEuripides Markou
Euripides Markou
APAndrzej Pelc
Andrzej Pelc
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 locating a black hole in a (partially) synchronous tree network, assuming an upper bound on the time of any edge traversal by an agent. The minimum number of agents capable of identifying a black hole is two. For a given tree and given starting node we are interested in the fastest-possible black hole search by two agents. For arbitrary trees we give a 5/3-approximation algorithm for this problem. We give optimal black hole search algorithms for two ‘extreme’ classes of trees: the class of lines and the class of trees in which any internal node (including the root which is the starting node) has at least two children.

11 July 2009 in Journal of Computer and System Sciences
Verified
Journal Article
Closed access
PFPierre Fraigniaud
Pierre Fraigniaud
DIDavid Ilcinkas
David Ilcinkas
APAndrzej Pelc
Andrzej Pelc

28 July 2006 in Discrete Mathematics
Verified
Journal Article
Open access
PDF file
TCTiziana Calamoneri
Tiziana Calamoneri
APAndrzej Pelc
Andrzej Pelc
RPRossella Petreschi
Rossella Petreschi
An L(h,k)-labeling of a graph G is an integer labeling of vertices of G, such that adjacent vertices have labels which differ by at least h, and vertices at distance two have labels which differ by at least k. The span of an L(h,k)-labeling is the difference between the largest and the smallest label. We investigate L(h,k)-labelings of trees of maximum degree Δ, seeking those with small span. Given Δ, h and k, span λ is optimal for the class of trees of maximum degree Δ, if λ is the smallest integer such that every tree of maximum degree Δ has an L(h,k)-labeling with span at most λ. For all parameters Δ,h,k, such that h<k, we construct L(h,k)-labelings with optimal span. We also establish optimal span of L(h,k)-labelings for stars of arbitrary degree and all values of h and k.