J. Czyzowicz, A. Pelc, I. Rival, J. Urrutia, Crooked diagrams with few slopes,
Order 7 (1990), pp. 133-143.
J. Czyzowicz, A. Pelc, I. Rival, J. Urrutia, Crooked diagrams with few slopes,
Order 7 (1990), pp. 133-143.
Abstract:
A natural and practical criterion in the preparation of diagrams of ordered sets is to minimize the number of different slopes used for the edges. For any diagram this is at least the maximum number of upper covers and of lower covers of any element. While this maximum degree is not always enough, we show that it is as long as any edge joining a covering pair may be bent, to produce a crooked diagram.
J. Czyzowicz, A. Pelc, I. Rival, Planar ordered sets of width two,
Mathematica Slovaca 40 (1990), pp. 375-388.
Abstract:
We give finite list of orders such that an order of width two is planar if and only if it does not contain a subdiagram a homeomorph of a member of this list. The proof of our result yields an O(n3/2) algorithm to test planarity of orders of width two with n vertices.
J. Czyzowicz, A. Pelc, I. Rival, Drawing orders with few slopes,
Discrete Mathematics 82 (1990), pp. 233-250.
Abstract:
It is common to draw a diagram of an ordered set with as few slopes as seem possible; the maximum number of upper covers or lower covers of an element is an obvious lower bound to the number of different slopes needed. We construct lattices with at most two (respectively, three) upper and lower covers which require at least three (respectively, four) different slopes - despite a conjecture of B. Sands to the contrary. Moreover, we characterize lattices with two-slope diagrams. It follows, for example, that every planar lattice with at most two upper and two lower covers has a (planar) two-slope diagram.
K. Diks, A. Pelc, Reliable gossip schemes with random link failures,
Proc. 28th Annual Allerton Conference on Communication, Control and
Computing,
Allerton, Illinois, October 1990, pp. 978-987.
Abstract:
Each of n people has a piece of information which should be communicated to everybody else. This is to be done by executing a sequence of two-party telephone calls in which the two participants exchange all information they currently have, in a unit of time. Two parameters to be minimized are: the total number of calls or the total time used. We study the following variation of this well-known gossip problem: assuming that telephone lines fail independently with constant probability 0 < p < 1 , find efficient schemes of calls which assure complete communication with probability converging to 1 as n grows. We show a non-adaptive scheme using O(n log n) calls and prove that it is asymptotically optimal. We also show an adaptive scheme whose expected number of calls in O(n). Moreover, two time-efficient schemes are proposed: a non-adaptive one using O(log2n) time units and an adaptive one working in expected time O(log n).
J. Czyzowicz, A. Pelc, I. Rival, Unfolding weighted consensus orders into consistent numerical scales,
in: Topics in Combinatorics and Graph Theory,
Essays in honour of Gerhard Ringel, R. Bodendiek and R. Henn (Eds.),
Physica-Verlag, Heidelberg 1990, pp. 207-217.
Abstract:
The aim of this paper is twofold: first, to introduce a new model in the factor analysis of preference data; second, to establish several related theoretical results about ordered sets, which seem to be of independent mathematical interest.