Chapter 11
Not So Perfect Graphs
Martin Charles Golumbic
Publisher Summary
This chapter discusses the sorting of a permutation using stacks in parallel. Let Π be a permutation of the numbers {1, 2, …, n}, which one regards as the sequence Π = [Π1, Π2, …, Πn). One likes to sort n into natural order using a system of stacks arranged in parallel is illustrated in the chapter. Initially, the permutation sits on the input queue. Two types of moves are allowed: (1) moving the number at the head of the input queue onto the top of one of the stacks or (2) moving a number from the top of a stack to the tail of the output queue. A successful sorting is accomplished by transferring all numbers to the output queue in the order [1, 2, …, n] by repeatedly applying ...
