A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
From MaRDI portal
Publication:1827809
DOI10.1016/j.dam.2003.07.001zbMath1042.05067OpenAlexW1990242495MaRDI QIDQ1827809
Publication date: 6 August 2004
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2003.07.001
Proper interval graphsUnit interval graphsGraph recognition algorithmLexicographic breadth first search
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (47)
Algorithms for finding disjoint path covers in unit interval graphs ⋮ Uniform embeddings for Robinson similarity matrices ⋮ Reconstruction of line-embeddings of graphons ⋮ The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs ⋮ A new LBFS-based algorithm for cocomparability graph recognition ⋮ Graph searches and their end vertices ⋮ Robinsonian matrices: recognition challenges ⋮ Perfect elimination orderings for symmetric matrices ⋮ Extending partial representations of interval graphs ⋮ Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number ⋮ A Characterization of Mixed Unit Interval Graphs ⋮ End-Vertices of Graph Search Algorithms ⋮ Polynomial kernels for proper interval completion and related problems ⋮ Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition ⋮ A tie-break model for graph search ⋮ A characterization of unit interval bigraphs of open and closed intervals ⋮ Balancing graph Voronoi diagrams with one more vertex ⋮ Unit and single point interval graphs ⋮ Integral mixed unit interval graphs ⋮ A new graph parameter to measure linearity ⋮ Fully dynamic representations of interval graphs ⋮ The complexity of finding uniform sparsest cuts in various graph classes ⋮ An Optimization Parameter for Seriation of Noisy Data ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Dynamic algorithms for monotonic interval scheduling problem ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ The Roberts characterization of proper and unit interval graphs ⋮ On the non-unit count of interval graphs ⋮ Recognizing Proper Tree-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 ⋮ Graphs of interval count two with a given partition ⋮ Mixed unit interval graphs ⋮ A Lex-BFS-based recognition algorithm for Robinsonian matrices ⋮ Recovering the structure of random linear graphs ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ Polynomial Kernels for Proper Interval Completion and Related Problems ⋮ A new representation of proper interval graphs with an application to clique-width ⋮ Short Models for Unit Interval Graphs ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ Uniquely Restricted Matchings in Interval Graphs ⋮ Linear time algorithms for finding sparsest cuts in various graph classes ⋮ Fully dynamic recognition of proper circular-arc graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear-time algorithm for proper interval graph recognition
- Simple linear time recognition of unit interval graphs
- A linear time recognition algorithm for proper interval graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Optimal greedy algorithms for indifference graphs
- On the compatibility between a graph and a simple order
- A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
