S. Leipert
Technical Report No. 97.259, Universität zu Köln, Germany. (1997)
Abstract
PQ-trees are a data structure being used to represent the permutations of a set U in which various subsets of U occur consecutively. Along with the data structure, efficient algorithms for manipulating PQ-trees are given, requiring linear time in the size of the input. An implementation of the PQ-trees as template class allows easy checking of the consecutive ones property, without letting the user worry about the details of the algorithm. More sophisticated algorithms as planarity testing and embedding, computing planar subgraphs or finding cuts in the TSP, require the manipulation of the data structure. Therefore an implementation of the PQ-trees has to support possible manipulations of the data structure. This makes the implementation of the data structure reusable and allows the user a fast adaption to other implementations.