Counting endpoint sequences for interval orders and interval graphs (Q685648)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Counting endpoint sequences for interval orders and interval graphs |
scientific article; zbMATH DE number 423562
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Counting endpoint sequences for interval orders and interval graphs |
scientific article; zbMATH DE number 423562 |
Statements
Counting endpoint sequences for interval orders and interval graphs (English)
0 references
24 October 1993
0 references
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 method to \(PQ\)-trees and \(MPQ\)-trees. Finally, we discuss the connection of these structures with temporal reasoning.
0 references
\(PQ\)-trees
0 references
\(MPQ\)-trees
0 references
endpoint sequences
0 references
interval graph
0 references
interval
0 references
temporal reasoning
0 references
0 references
