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