Greedy linear extensions for minimizing bumps

Let P be a finite poset and let L={x ₁<...n} be a linear extension of P. A bump in L is an ordered pair (x _i , x _i+1) where x _ii+1 in P. The bump number of P is the least integer b(P), such that there exists a linear extension of P with b(P) bumps. We call L optimal if the number of bumps of L is b(P). We call L greedy if x _{i j} for every j>i, whenever (x _i, x _i+1) is a bump. A poset P is called greedy if every greedy linear extension of P is optimal. Our main result is that in a greedy poset every optimal linear extension is greedy. As a consequence, we prove that every greedy poset of bump number k is the linear sum of k+1 greedy posets, each of bump number zero.This research (Math/1406/31) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

Minimizing bumps in linear extensions of ordered sets

A linear extension x ₁ x ₂ x ₃ ... of a partially ordered set (X, <) has a bump whenever x _i <x _i +1. We examine the problem of determining linear extensions with as few bumps as possible. Heuristic algorithms for approximate bump minimization are considered.     

NP-completeness properties about linear extensions

Following the pioneering work of Kierstead, we present here some complexity results about the construction of depth-first greedy linear extensions. We prove that the recognition of Dilworth partially ordered sets of height 2, as defined by Syslo, is NP-complete. This last result yields a new proof of the NP-completeness of the jump number problem, first proved by Pulleyblank.     

Counting linear extensions

We survey the problem of counting the number of linear extensions of a partially ordered set. We show that this problem is #P-complete, settling a long-standing open question. This result is contrasted with recent work giving randomized polynomial-time algorithms for estimating the number of linear extensions.One consequence of our main result is that computing the volume of a rational polyhedron is strongly #P-hard. We also show that the closely related problems of determining the average height of an element x of a give poset, and of determining the probability that x lies below y in a random linear extension, are #P-complete.Research carried out while this author was visiting Bellcore under the auspices of DIMACS.     

On the size of jump-critical ordered sets

The maximum size of a jump-critical ordered set with jump-number m is at most (m+1)!     

On minimizing the jump number for interval orders

The purpose of this paper is to give an effective characterization of all interval orders which are greedy with respect to the jump number problem.This research (Math/1406/30) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

The jump number of suborders of the power set order

Let P be an ordered set induced by several levels of a power set. We give a formula for the jump number of P and show that reverse lexicographic orderings of P are optimal. The proof is based on an extremal set result of Frankl and Kalai.     

Greedy posets for the bump-minimizing problem

A bump (x _i,x _i+1) occurs in a linear extension L={x ₁<...n} of a poset P, if x _ii+1 in P. L. is greedy if x _ij for every j>i, whenever (x _i x _i+1) in a bump in L. The purpose of this paper is to give a characterization of all greedy posets. These are the posets for which every greedy linear extension has a minimum number of bumps.This research (Math/1406/31) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

The jump number of Z-free ordered sets

An ordered set P is called Z-free if it does not contain a four-element subset {a, b, c, d} such that a and c are the only comparabilities among these elements. In this paper we present a polynomial algorithm to find the jump number of finite Z-free ordered sets and that of their duals.     

A linear time algorithm to find the jump number of 2-dimensional bipartite partial orders

Let L=u ₁ , u ₂ , ..., u _k be a linear extension of a poset P. Each pair (u _i , u _i+1 ) of unrelated elements in P is called a jump of L. The jump number problem is to find L with the minimum number of jumps. The problem is known to be NP-hard even on bipartite posets. Here we present a linear time algorithm for it in 2-dimensional bipartite posets. We also discuss briefly some weighted cases.     

On the greedy dimension of a partial order

This paper introduces a new concept of dimension for partially ordered sets. Dushnik and Miller in 1941 introduced the concept of dimension of a partial order P, as the minimum cardinality of a realizer, (i.e., a set of linear extensions of P whose intersection is P). Every poset has a greedy realizer (i.e., a realizer consisting of greedy linear extensions). We begin the study of the notion of greedy dimension of a poset and its relationship with the usual dimension by proving that equality holds for a wide class of posets including N-free posets, two-dimensional posets and distributive lattices.     

Substitution and atomic extension on greedy posets

In this paper, we study the operations of substitution and atomic extension on greedy posets. For the substitution operation, if P=(P ₁ , x, P ₂ )is a greedy poset, then P ₁ and P ₂ are greedy posets, the converse being false. However, for the atomic extension, P=P ₁ (x, P ₂ )is a greedy poset if and only if P ₁ and P ₂ are greedy posets. We prove also that the class of greedy semi-partitive lattices is the smallest one containing M _n (n2), B ₃ and closed by atomic extension. The class C _n of greedy posets with jump number n is infinite. However, we show that C _n can be obtained, in a very simple way, from a subclass D _n of finite cardinal ity. We construct D _n for n=1, 2.     

On finding the jump number of a partial orber by substitution decomposition

Consider the linear extensions of a partial order. A jump occurs in a linear extension if two consecutive elements are unrelated in the partial order. The jump number problem is to find a linear extension of the ordered set which contains the smallest possible number of jumps. We discuss a decomposition approach for this problem from an algorithmic point of view. Based on this some new classes of partial orders are identified, for which the problem is polynomially solvable.     

Representing orders on the plane by translating convex figures

Given a finite collection of disjoint, convex figures on the plane, is it possible to assign to each a single direction of motion so that this collection of figures may be separated, through an arbitrary large distance, by translating each figure one at a time, along its assigned direction? We present a computational model for this separability problem based on the theory of ordered sets.     

On computing the number of linear extensions of a tree

An algorithm requiring O(n ²) arithmetic operations for computing the number of linear extensions of a poset whose covering graph is a tree is given.This research was partially funded by the National Science and Engineering Research Council of Canada under Grant Number A4219.     

Cycle-free partial orders and chordal comparability graphs

This paper studies a number of problems on cycle-free partial orders and chordal comparability graphs. The dimension of a cycle-free partial order is shown to be at most 4. A linear time algorithm is presented for determining whether a chordal directed graph is transitive, which yields an O(n ²) algorithm for recognizing chordal comparability graphs. An algorithm is presented for determining whether the transitive closure of a digraph is a cycle-free partial order in O(n+m _t)time, where m _tis the number of edges in the transitive closure.     

Scheduling tasks with communication delays on parallel processors

LetP={v ₁,...,v _n } be a set ofn jobs to be executed on a set ofm identical machines. In many instances of scheduling problems, if a jobv _i has to be executed before the jobv _j and both jobs are to be executed on different machines, some sort of information exchange has to take place between the machines executing them. The time it takes for this exchange of information is called a communication delay.In this paper we give anO(n) algorithm to find an optimal scheduling with communication delays when the number of machines is not limited and the precedence constraints on the jobs form a tree.     

Computing on-line the lattice of maximal antichains of posets

We consider the on-line computation of the lattice of maximal antichains of a finite poset . This on-line computation satisfies what we call the linear extension hypothesis: the new incoming vertex is always maximal in the current subposet of . In addition to its theoretical interest, this abstraction of the lattice of antichains of a poset has structural properties which give it interesting practical behavior. In particular, the lattice of maximal antichains may be useful for testing distributed computations, for which purpose the lattice of antichains is already widely used. Our on-line algorithm has a run time complexity of , where |P| is the number of elements of the poset, , |MA(P)| is the number of maximal antichains of and (P) is the width of . This is more efficient than the best off-line algorithms known so far.     

A recurrence for linear extensions

The number e(P) of linear extensions of a finite poset P is expressed in terms of e(Q) for certain smaller posets Q. The proof is based on M. Schützengerger's concept of promotions of linear extensions.Partially supported by NSF Grant #DMS-8700995.Partially supported by NSF Grant #DMS-8401376.     

Antichain sequences

For any finite partially ordered set S we display a dual transportation system of linear inequalities, and a bijection A(x) from the maximal integer-valued solutions x of this system onto the maximal sequences of k antichains in S. This provides a simple translation to a dual transportation problem of the problem: find a maximum weight union of k antichains.Research supported by the Natural Sciences and Engineering Research of Canada.