PQ-Trees, An Implementation as Template Class in C++

Leipert, Sebastian (1997) PQ-Trees, An Implementation as Template Class in C++.
Technical Report , 226 p.


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.

Download: [img] Postscript
Download (1MB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-259
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:45
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/259