Simple linear time recognition of unit interval graphs

DOI10.1016/0020-0190(95)00046-FzbMATH Open0875.68690MaRDI QIDQ672408FDOQ672408

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)

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

zbMATH Keywords

Graph algorithmsDesign of algorithmsBreadth-first searchInterval graphsProper interval graphsUnit interval graphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (67)

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