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)

zbMATH Keywords

intervaltemporal reasoninginterval graph\(MPQ\)-trees\(PQ\)-treesendpoint sequences

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Counting Interval Graphs
• 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)