Simple linear time recognition of unit interval graphs

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

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