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