Arrow Research search

Author name cluster

Danny Krizanc

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

21 papers
2 author rows

Possible papers

21

MFCS Conference 2005 Conference Paper

Asynchronous Deterministic Rendezvous in Graphs

  • Gianluca De Marco
  • Luisa Gargano
  • Evangelos Kranakis
  • Danny Krizanc
  • Andrzej Pelc
  • Ugo Vaccaro

Abstract Two mobile agents (robots) having distinct labels and located in nodes of an unknown anonymous connected graph, have to meet. We consider the asynchronous version of this well-studied rendezvous problem and we seek fast deterministic algorithms for it. Since in the asynchronous setting meeting at a node, which is normally required in rendezvous, is in general impossible, we relax the demand by allowing meeting of the agents inside an edge as well. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of edge traversals of both agents until rendezvous is achieved. If agents are initially situated at a distance D in an infinite line, we show a rendezvous algorithm with cost O ( D | L min | 2 ) when D is known and O (( D + | L max |) 3 ) if D is unknown, where | L min | and | L max | are the lengths of the shorter and longer label of the agents, respectively. These results still hold for the case of the ring of unknown size but then we also give an optimal algorithm of cost O ( n | L min |), if the size n of the ring is known, and of cost O ( n | L max |), if it is unknown. For arbitrary graphs, we show that rendezvous is feasible if an upper bound on the size of the graph is known and we give an optimal algorithm of cost O ( D | L min |) if the topology of the graph and the initial positions are known to agents.

Details

MFCS Conference 1996 Conference Paper

Minimizing Congestion of Layouts for ATM Networks with Faulty Links

  • Leszek Gasieniec
  • Evangelos Kranakis
  • Danny Krizanc
  • Andrzej Pelc

Abstract We consider the problem of constructing virtual path layouts for an ATM network consisting of a complete network K n 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 layouts and have a least possible congestion. First, we study the minimal congestion of 1-hop f -tolerant layouts in K n. 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 K n [ \(\mathcal{F}\) ] which results from K n by deleting links from a set \(\mathcal{F}\) of bounded size. Next we study the minimal congestion of h -hop f -tolerant layouts in K n, 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. 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 such layouts in K n, with congestion O (log n ).

Details

MFCS Conference 1995 Conference Paper

String Recognition on Anonymous Rings

  • Evangelos Kranakis
  • Danny Krizanc
  • Flaminia L. Luccio

Abstract We consider the problem of recognizing whether a given binary string of length n is equal (up to rotation) to the input of an anonymous oriented ring of n processors. Previous algorithms for this problem have been “global” and do not take into account “local” patterns occurring in the string. Such patterns may be repetitive or discriminating, and can be used to provide efficient algorithms for recognizing strings. In this paper we give new upper and lower bounds on the bit complexity of string recognition. For the case of periodic strings, near optimal bounds are given which depend on the period of the string. For the case of a randomly chosen string, an optimal algorithm for the problem is given. In particular, we show that almost all strings can be recognized by communicating θ(n log n) bits. It is interesting to note that Kolmogorov complexity theory is used in the proof of our upper bound, rather than its traditional application to the proof of lower bounds.

Details

FOCS Conference 1993 Conference Paper

Universal Emulations with Sublogarithmic Slowdown

  • Christos Kaklamanis
  • Danny Krizanc
  • Satish Rao

The existence of bounded degree networks which can emulate the computation of any bounded degree network of the same size with logarithmic slowdown is well-known. The butterfly is an example of such a universal network. Leiserson was the first to introduce the concept of an area-universal network: a network with VLSI layout area A which can emulate any network of the same size and layout area with logarithmic slowdown. His results imply the existence of an N-node network with layout area O(N log/sup 2/ N) which can emulate any N-node planar network with O(log N) slowdown. The main results of this paper are: There exists an N-node network with layout area O(N log/sup 2/ N) which can emulate any N-node planar network with O(loglogN) slowdown. The N-node butterfly (and hypercube) can emulate any network with VLSI layout area N/sup 2-/spl epsiv// (/spl epsiv/>0) with O(loglogN) slowdown. We also discuss sublogarithmic bounds for the slowdown of emulations of arbitrary bounded degree networks. >

Details

FOCS Conference 1987 Conference Paper

The Complexity of Parallel Comparison Merging

  • Mihály Geréb-Graus
  • Danny Krizanc

We prove a worst case lower bound of Ω(log log n) for randomized algorithms merging two sorted lists of length n in parallel using n processors on Valiant's parallel computation tree model. We show how to strengthen this result to a lower bound for the expected time taken by any algorithm on the uniform distribution. Finally, bounds are given for the average time required for the problem when the number of processors is less than and greater than n.

Details