From: Frank Ruskey <fruskey@csr.uvic.ca>
Newsgroups: sci.math,comp.theory
Subject: Re: Compute # of total extensions of a finite poset
Date: Mon, 16 Feb 1998 16:08:40 -0800

Apollo Hogan wrote:
> 
> In article <6c2jt5$1et$1@uwm.edu>, Vu A. Ha <vu@cs.uwm.edu> wrote:
> >Dear colleagues,
> >
> >I am looking for an efficient algorithm to compute the number
> >of total extensions of a finite poset.
> >
> >In another formulation, the problem is how to count the number
> >of topological (or ancestral) orders of a directed acyclic graph.
> >A topological order of a DAG is an ordering of its vertices
> >{v_1,...v_n} such that for all edges v_i <-- v_j of the DAG, i<j.
> >
> >Another question I'd like to ask is: what are the most common ways
> >to define similarity measures on the set of directed acyclic graphs
> >over n vertices?
> >
> >Any idea or reference will be greatly appreciated!
> >Regards, Vu~
> 
> Here are some more references to the problem:
> 
> Kalvin, A. and Varol, Y. "On the generation of all topological sortings."
>         Journal of Algorithms. 4. 150-162. 1983.
> 
> Bouchitte, V. and Habib, M. "NP-completeness properties about linear
>         extensions." Order. 4. 143-154. 1987.
> Abstract:
>         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 jump
>         number problem, first proved by Pulleyblank.
> 
> Sidorenko, A. "Inequalities for the number of linear extensions."
>         Order. 8. 331-340. 1992.
> 
> Stachoviak, G. "A relation between the comparability graph and the number
>         of linear extensions."
>         Order. 6. 241-244. 1989.
> 
> --Apollo Hogan
> 
> --
> Professional Research Assistant
> Dr. Elizabeth Bradley, Dept. of Computer Science
> University of Colorado, Boulder

You might want to take a look at the Combinatorial Object
Server information page:
http://sue.csc.uvic.ca/~cos/inf/pose/LinearExt.html
and the corresponding generation page:
http://sue.csc.uvic.ca/~cos/gen/pose.html
From  the information page you can download my recursive
implementation of the Varol-Rotem algorithm and of
the Gray Code algorithm of Gara Pruesse and myself, Generating Linear
Extensions Fast, SIAM J. Computing, 23 (1994), 373-386.
On the generation page you can input a poset and it will 
return the number of extensions.

-- 
Frank Ruskey                     e-mail: fruskey@csr.uvic.ca
Dept. of Computer Science        fax:    250-721-7292
University of Victoria           office: 250-721-7232
Victoria, B.C. V8W 3P6 CANADA    WWW: http://www.csc.uvic.ca/~fruskey