ISSN:
1572-9273
Keywords:
06A07
;
68Q15
;
68P05
;
05A05
;
Loop-free algorithms
;
linear extensions
;
#P-complete
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract A precise concept of when a combinatorial counting problem is “hard” was first introduced by Valiant (1979) when he defined the notion of a #P-complete problem. Correspondingly, there has been consistent interest in the notion of when a combinatorial listing problem admits a very special regular structure in which transition times between objects being listed are uniformly bounded by a fixed constant. Early descriptions of suchloop-free listing algorithms may be found in the bookAlgorithmic Combinatorics by Even (1973). Recently, the problem of counting all linear extensions of a partially ordered set has received attention with regard to both of these combinatorial concepts. Brightwell and Winkler (1991) have shown, by a very ingenious argument, that the poset-extension counting problem is #P-complete. Pruesse and Ruskey (1992) have shown that the corresponding listing problem can be solved in constant amortized time and have posed the problem of finding a loop-free algorithm for the poset-extension problem. The present paper presents a solution to this latter problem. This sequence of results represents an interesting juxtaposition, in a fixed, naturally-occurring combinatorial problem, of intricate and precisely defined “irregularities” with respect to counting with very strong regularities with respect to listing.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01108590
Permalink
