Counting endpoint sequences for interval orders and interval graphs

Abstract

In this paper we design and analyze efficient algorithms for counting the number of endpoint sequences representing a given interval graph or interval order. The results are based on the construction of a suitable tree data structure to represent multiple solutions. We describe the relation of our methods to PQ-trees and MPQ-trees. Finally, we discuss the connection of these structures with temporary reasoning. © 1993.