From: Frank Ruskey
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 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 >
> >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