On-line recognition of interval graphs in \(O(m+n \log n)\) time

DOI10.1007/3-540-61576-8_70zbMATH Open1540.68183MaRDI QIDQ6567667

Wenlian Hsu

Publication date: 5 July 2024

zbMATH Keywords

interval graphonline algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incidence matrices and interval graphs
• On Comparability and Permutation Graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs

This page was built for publication: On-line recognition of interval graphs in \(O(m+n \log n)\) time