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

DOI10.1007/3-540-61576-8_70MaRDI QIDQ6567667zbMATH OpenFDO

Authors Wenlian Hsu

Publication date 5 July 2024

zbMATH Keywords

online algorithminterval graph

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4049085
• scientific article; zbMATH DE number 512914
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• scientific article; zbMATH DE number 176590
• A linear-time algorithm for proper interval graph recognition

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3679885 (Why is no real title available?)
• scientific article; zbMATH DE number 512914 (Why is no real title available?)
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Incidence matrices and interval graphs
• On Comparability and Permutation Graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

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

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