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

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

Authors: Wenlian Hsu 

Publication date: 5 July 2024

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

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)

Cites Work

• 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
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• On Comparability and Permutation Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

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)