Simple linear time recognition of unit interval graphs

DOI10.1016/0020-0190(95)00046-FzbMath0875.68690MaRDI QIDQ672408

Hiryoung Kim, Stephan Olariu, Sridhar Natarajan, Alan P. Sprague, Derek Gordon Corneil

Publication date: 28 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

Graph algorithmsDesign of algorithmsInterval graphsBreadth-first searchProper interval graphsUnit interval graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (61)

Algorithms for finding disjoint path covers in unit interval graphs ⋮ Uniform embeddings for Robinson similarity matrices ⋮ On partitioning interval graphs into proper interval subgraphs and related problems ⋮ Recognizing \(d\)-interval graphs and \(d\)-track interval graphs ⋮ On unit interval graphs with integer endpoints ⋮ Proper interval graphs and the guard problem ⋮ Threshold-coloring and unit-cube contact representation of planar graphs ⋮ \(O(1)\) query time algorithm for all pairs shortest distances on permutation graphs ⋮ Recognizing and representing proper interval graphs in parallel using merging and sorting ⋮ Polynomial kernels for proper interval completion and related problems ⋮ Characterizing interval graphs which are probe unit interval graphs ⋮ Corrigendum to: ``Complexity and approximability of the happy set problem ⋮ Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition ⋮ On the recognition of fuzzy circular interval graphs ⋮ Maximum cut on interval graphs of interval count four is NP-complete ⋮ An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs ⋮ Integral mixed unit interval graphs ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ Fully dynamic representations of interval graphs ⋮ Computing role assignments of proper interval graphs in polynomial time ⋮ A fully dynamic graph algorithm for recognizing interval graphs ⋮ Approximating the path-distance-width for AT-free graphs and graphs in related classes ⋮ An Optimization Parameter for Seriation of Noisy Data ⋮ Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory ⋮ Induced subgraph isomorphism on proper interval and bipartite permutation graphs ⋮ Lower and upper bounds for the linear arrangement problem on interval graphs ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ The Roberts characterization of proper and unit interval graphs ⋮ On the classes of interval graphs of limited nesting and count of lengths ⋮ Template-driven rainbow coloring of proper interval graphs ⋮ A linear-time algorithm for proper interval graph recognition ⋮ Recognition and characterization of unit interval graphs with integer endpoints ⋮ Extending partial representations of proper and unit interval graphs ⋮ Unit Interval Graphs of Open and Closed Intervals ⋮ A structural characterization for certifying Robinsonian matrices ⋮ Powers of cycles, powers of paths, and distance graphs ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Unnamed Item ⋮ Template-driven rainbow coloring of proper interval graphs ⋮ A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs ⋮ Mixed unit interval graphs ⋮ A simple algorithm to find Hamiltonian cycles in proper interval graphs ⋮ A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs ⋮ A Lex-BFS-based recognition algorithm for Robinsonian matrices ⋮ Recovering the structure of random linear graphs ⋮ Mutual exclusion scheduling with interval graphs or related classes. I ⋮ Linear time algorithms to solve the linear ordering problem for oriented tree based graphs ⋮ Paired threshold graphs ⋮ A linear time recognition algorithm for proper interval graphs ⋮ Localized and compact data-structure for comparability graphs ⋮ Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs ⋮ Approximability of the Path-Distance-Width for AT-free Graphs ⋮ A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs ⋮ A new representation of proper interval graphs with an application to clique-width ⋮ Short Models for Unit Interval Graphs ⋮ A dynamic distributed approach to representing proper interval graphs ⋮ O(1) QUERY TIME ALGORITHM FOR ALL PAIRS SHORTEST DISTANCES ON INTERVAL GRAPHS ⋮ Extending partial representations of subclasses of chordal graphs ⋮ Sitting closer to friends than enemies, revisited ⋮ A polynomial algorithm for the k-cluster problem on the interval graphs ⋮ Fully dynamic recognition of proper circular-arc graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Scott-Suppes theorem on semiorders
• Foundational aspects of theories of measurement
• Computing the Bandwidth of Interval Graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Measurement Theory

This page was built for publication: Simple linear time recognition of unit interval graphs