A. Pelc, I. Rival, Orders with level diagrams,
European Journal of Combinatorics 12 (1991), pp. 61-68.
A. Pelc, I. Rival, Orders with level diagrams,
European Journal of Combinatorics 12 (1991), pp. 61-68.
Abstract:
We prove that a finite ordered set has a diagram in which, for each element, all upper covers are on a horizontal level, iff the ordered set contains no alternating cover cycle. We also show how to efficiently draw such horizontally aligned diagrams if they exist.
J. Czyzowicz, K. B. Lakshmanan, A. Pelc, Searching with a forbidden lie pattern in responses,
Information Processing Letters 37 (1991), pp. 127-132.
Abstract:
Ulam suggested the following two-person game. The Responder chooses an element x in an n-element set S and the Questioner has to find it by stating queries of the form `` Does x belong to T?'', where T is a subset of S. Some answers of the Responder may be false.
By specifying the restrictions on Responder's lies, various ``searching games with errors'' can be defined. Most attention in the literature was devoted to restrictions of global type, e.g., upper bounds on the total number of lies. In this paper we focus on constraints of local type, by forbidding a specific pattern of errors. Any sequence of true/lie responses can be encoded as a binary sequence whose ith term is 0 (1) if the ith answer is true (false). For example, forbidding the pattern 11 means that the Responder cannot lie twice successively. We show that search is feasible only for four forbidden patterns: 0, 1, 01, and 10. For these four cases we present worst-case optimal search algorithms.
A. Pelc, Broadcasting in complete networks with faulty nodes using unreliable calls,
Information Processing Letters 40 (1991), pp. 169-174.
Abstract:
Assuming that nodes in a complete communication network fail with constant probability p < 1, individual calls fail with constant probability q < 1 and all failures are independent, we give an algorithm which broadcasts information from a given fault-free node to all other fault-free nodes, with probability converging to 1, as the number of nodes grows. The algorithm works in expected logarithmic time.
A. Pelc, Undirected graph models for system-level fault diagnosis,
IEEE Transactions on Computers 40 (1991), pp. 1271-1276.
Abstract:
We consider two comparison based diagnosis models previously introduced by Chwa and Hakimi and by Malek. For each of them we study classical t-diagnosability and probabilistic diagnosability based on the maximum likelihood principle. We also introduce a new probabilistic model for comparison testing. In all considered models we design optimal diagnosable systems, i.e., those which use the least possible number of testing links. These systems have a linear number of links and can be diagnosed in linear time. We prove, however, that for general systems, both diagnosis and diagnosability problems are NP-hard.
F. Al-Thukair, A. Pelc, I. Rival, J. Urrutia, Motion-planning, two-directional point representations and ordered sets,
SIAM Journal on Discrete Mathematics 4 (1991), pp. 151-163.
Abstract:
Ordered sets are used as a computational model for motion planning problems. Every ordered set has a two-directional point representation using subdivision. These subdivision points correspond to direction changes along the path of motion.
B. S. Chlebus, K. Diks, A. Pelc, Optimal broadcasting in faulty hypercubes,
Proc. 21st Annual International Symposium on Fault-Tolerant Computing,
Montreal, Canada, June 1991, pp. 266-273.
Abstract:
We consider the problem of broadcasting information in an n-node hypercube in which links fail independently with fixed probability 0 < p < 1. Information originally held by one node has to be disseminated throughout the network. Messages can be transmitted along links and in a unit of time every node can transmit to at most one neighbor. Transmissions via faulty links do not succeed. We develop a broadcasting algorithm that disseminates information throughout the whole network in time a log n, with probability exceeding1 - bn-c , with positive constants a, b, c depending on p, provided that p < 9%.