Simple linear time recognition of unit interval graphs

DOI10.1016/0020-0190(95)00046-FMaRDI QIDQ672408zbMATH OpenFDO

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

Publication date 28 February 1997

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

Full work available at URL https://doi.org/10.1016/0020-0190(95)00046-F

zbMATH Keywords

Breadth-first searchDesign of algorithmsGraph algorithmsInterval graphsProper interval graphsUnit interval graphs

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4049085
• A linear time recognition algorithm for proper interval graphs
• scientific article; zbMATH DE number 176590
• A linear-time algorithm for proper interval graph recognition
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Strictly interval graphs: characterization and linear time recognition
• Linear recognition of almost interval graphs
• A polynomial time recognition algorithm for probe interval graphs

Cites work

• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• Computing the Bandwidth of Interval Graphs
• Foundational aspects of theories of measurement
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3706451 (Why is no real title available?)
• scientific article; zbMATH DE number 512914 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Measurement Theory
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Scott-Suppes theorem on semiorders

Cited in

(69)

• Mutual exclusion scheduling with interval graphs or related classes. I
• A linear time recognition algorithm for proper interval graphs
• Localized and compact data-structure for comparability graphs
• A dynamic distributed approach to representing proper interval graphs
• Proper interval graphs and the guard problem
• On properties of unit interval graphs with a perceptual motivation
• Fully dynamic representations of interval graphs
• On the classes of interval graphs of limited nesting and count of lengths
• Recognition and characterization of unit interval graphs with integer endpoints
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Recovering the structure of random linear graphs
• Paired threshold graphs
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Integral mixed unit interval graphs
• Normal Helly circular-arc graphs and its subclasses
• A fully dynamic graph algorithm for recognizing interval graphs
• A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
• A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
• Extending partial representations of subclasses of chordal graphs
• Sitting closer to friends than enemies, revisited
• Fully dynamic recognition of proper circular-arc graphs
• Recognizing d-interval graphs and d-track interval graphs
• Characterizing interval graphs which are probe unit interval graphs
• Approximating the path-distance-width for AT-free graphs and graphs in related classes
• The Roberts characterization of proper and unit interval graphs
• Algorithms for finding disjoint path covers in unit interval graphs
• Linear time algorithms to solve the linear ordering problem for oriented tree based graphs
• A new representation of proper interval graphs with an application to clique-width
• Short models for unit interval graphs
• Unit interval graphs: a story with open ends
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. I: Theory
• The LBFS structure and recognition of interval graphs
• Approximability of the path-distance-width for AT-free graphs
• On partitioning interval graphs into proper interval subgraphs and related problems
• On unit interval graphs with integer endpoints
• A polynomial algorithm for the k-cluster problem on the interval graphs
• Threshold-coloring and unit-cube contact representation of planar graphs
• A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
• Polynomial kernels for proper interval completion and related problems
• On the recognition of fuzzy circular interval graphs
• Unit and single point interval graphs
• Computing role assignments of proper interval graphs in polynomial time
• Lower and upper bounds for the linear arrangement problem on interval graphs
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Unit interval graphs of open and closed intervals
• Maximal neighborhood search and rigid interval graphs
• A four-sweep LBFS recognition algorithm for interval graphs
• O(1) QUERY TIME ALGORITHM FOR ALL PAIRS SHORTEST DISTANCES ON INTERVAL GRAPHS
• A structural characterization for certifying Robinsonian matrices
• Powers of cycles, powers of paths, and distance graphs
• Similarity-first search: a new algorithm with application to Robinsonian matrix recognition
• An optimization parameter for seriation of noisy data
• Template-driven rainbow coloring of proper interval graphs
• Template-driven rainbow coloring of proper interval graphs
• Corrigendum to: ``Complexity and approximability of the happy set problem
• 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
• Exactly hittable interval graphs
• A linear-time algorithm for proper interval graph recognition
• Realizability of free spaces of curves
• The convex set forming game
• Realizability of free spaces of curves
• Mixed unit interval graphs
• Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
• Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs
• Uniform embeddings for Robinson similarity matrices
• \(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
• A simple algorithm to find Hamiltonian cycles in proper interval graphs

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

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