Counting endpoint sequences for interval orders and interval graphs

DOI10.1016/0012-365X(93)90353-UMaRDI QIDQ685648zbMATH OpenWikidataFDO

Authors Alexander Belfer, Martin Charles Golumbic

Publication date 24 October 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(93)90353-U

zbMATH Keywords

\(MPQ\)-trees\(PQ\)-treesendpoint sequencesintervalinterval graphtemporal reasoning

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Graph theory (including graph drawing) in computer science (68R10)

Review text

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.

Recommendations

• Counting interval orders
• Chronological orderings of interval graphs
• Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph
• Parallel interval order recognition and construction of interval representations
• Chronological orderings of interval digraphs

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Counting Interval Graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Incidence matrices and interval graphs
• Incidence matrices, interval graphs and seriation in archeology
• Interval graphs and interval orders
• Interval graphs and related topics
• Maintaining knowledge about temporal intervals
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(1)

• Transitive closure for restricted classes of partial orders

This page was built for publication: Counting endpoint sequences for interval orders and interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685648)