Arrow Research search

Author name cluster

T. Radzik

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.

2 papers
1 author row

Possible papers

2

I&C Journal 1991 Journal Article

Connectivity vs. reachability

  • M. Chrobak
  • H. Karloff
  • T. Radzik

We consider the problem of the relative complexity of the connectivity and reachability (s-t-connectivity) problems, in a model resembling the one used for graph properties. In our model an oracle answers queries about edge-induced subgraphs, and we count the number of queries made. The main result is that in order to determine whether t is reachable from s one has to ask Ω(n2) questions about the connectivity of edge-induced subgraphs. For non-adaptive strategies we show that n 2 questions are necessary for n≥6. Several other results are included.

Details DOI

I&C Journal 1991 Journal Article

Improved deterministic parallel integer sorting

  • P.C.P. Bhatt
  • K. Diks
  • T. Hagerup
  • V.C. Prasad
  • T. Radzik
  • S. Saxena

We consider the problem of deterministic sorting of integers on a parallel RAM (PRAM). The best previous result (T. Hagerup, 1987, Inform. and Comput. 75, 39–51) states that n integers of size polynomial in n can be sorted in time O(log n) on a Priority CRCW PRAM with O( n log log n log n ) processors. We prove that n integers drawn from a set {0, …, m−1} can be sorted on an Arbitrary CRCW PRAM in time O( log n log log n + log log m) with a time-processor product of O(n log log m). In particular, if m = n (log n) O(1), the time and number of processors used are O( log n log log n ) and O( n(log log n)2 log n ), respectively. This improves the previous result in several respects: The new algorithm is faster, it works on a weaker PRAM model, and it is closer to optimality for input numbers of superpolynomial size. If log log m = O( log n log log n ), the new algorithm is optimally fast, for any polynomial number of processors, and if log log m = (1 + Ω(1)) log log n and log log m = 0( log n ), it has optimal speedup relative to the fastest known sequential algorithm. The space needed is O(nm ε ), for arbitrary but fixed ε > 0. The sorting algorithm derives its speed from a fast solution to a special list ranking problem of possible independent interest, the monotonic list ranking problem. In monotonic list ranking, each list element has an associated key, and the keys are known to increase monotonically along the list. We show that monotonic list ranking problems of size n can be solved optimally in time O( log n log log n ). We also discuss and attempt to solve some of the problems arising in the precise description and implementation of parallel recursive algorithms. As part of this effort, we introduce a new PRAM variant, the allocated PRAM.

Details DOI
v2026.09.13