Counting endpoint sequences for interval orders and interval graphs

DOI10.1016/0012-365X(93)90353-UzbMATH Open0781.68089WikidataQ127952212 ScholiaQ127952212MaRDI QIDQ685648FDOQ685648

Authors: Alexander Belfer, Martin Charles Golumbic 

Publication date: 24 October 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

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

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)

Cites Work

• Maintaining knowledge about temporal intervals
• Title not available (Why is that?)
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incidence matrices and interval graphs
• Incidence matrices, interval graphs and seriation in archeology
• A Characterization of Comparability Graphs and of Interval Graphs
• Interval graphs and interval orders
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Counting Interval Graphs
• Interval graphs and related topics

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)