A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
From MaRDI portal
Publication:1827809
DOI10.1016/J.DAM.2003.07.001zbMATH Open1042.05067OpenAlexW1990242495MaRDI QIDQ1827809FDOQ1827809
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
Recommendations
- A four-sweep LBFS recognition algorithm for interval graphs
- The LBFS structure and recognition of interval graphs
- scientific article
- Simple linear time recognition of unit interval graphs
- scientific article
- A linear-time algorithm for proper interval graph recognition
- scientific article; zbMATH DE number 1303554
- A linear time recognition algorithm for proper interval graphs
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- A fully dynamic graph algorithm for recognizing interval graphs
Proper interval graphsUnit interval graphsGraph recognition algorithmLexicographic breadth first search
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Cites Work
- Title not available (Why is that?)
- Optimal greedy algorithms for indifference graphs
- On the compatibility between a graph and a simple order
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Title not available (Why is that?)
- Simple linear time recognition of unit interval graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph-Theoretic Concepts in Computer Science
- Title not available (Why is that?)
- A linear-time algorithm for proper interval graph recognition
- Title not available (Why is that?)
- A Fully dynamic algorithm for recognizing and representing proper interval graphs
- A linear time recognition algorithm for proper interval graphs
- Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
Cited In (50)
- Recognizing LBFS trees of bipartite graphs
- Polynomial kernels for proper interval completion and related problems
- Linear time algorithms for finding sparsest cuts in various graph classes
- Robinsonian matrices: recognition challenges
- 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
- An Optimization Parameter for Seriation of Noisy Data
- A structural characterization for certifying Robinsonian matrices
- A new representation of proper interval graphs with an application to clique-width
- Fully dynamic recognition of proper circular-arc graphs
- Extending partial representations of interval graphs
- On the power of graph searching for cocomparability graphs
- Graphs of interval count two with a given partition
- The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs
- Unit and single point interval graphs
- A Characterization of Mixed Unit Interval Graphs
- A Lex-BFS-based recognition algorithm for Robinsonian matrices
- Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
- Reconstruction of line-embeddings of graphons
- Perfect elimination orderings for symmetric matrices
- Recognizing Proper Tree-Graphs
- A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
- The complexity of finding uniform sparsest cuts in various graph classes
- A characterization of unit interval bigraphs of open and closed intervals
- Polynomial Kernels for Proper Interval Completion and Related Problems
- A survey of the algorithmic aspects of modular decomposition
- Graph searches and their end vertices
- On the non-unit count of interval graphs
- Unit Interval Graphs of Open and Closed Intervals
- A tie-break model for graph search
- Balancing graph Voronoi diagrams with one more vertex
- Recovering the structure of random linear graphs
- Dynamic algorithms for monotonic interval scheduling problem
- On characterization and recognition of proper tagged probe interval graphs
- A new LBFS-based algorithm for cocomparability graph recognition
- Semi-proper interval graphs
- The Roberts characterization of proper and unit interval graphs
- Mixed unit interval graphs
- End-Vertices of Graph Search Algorithms
- Uniquely Restricted Matchings in Interval Graphs
- Unit interval graphs: a story with open ends
- Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number
- A new graph parameter to measure linearity
- Fully dynamic representations of interval graphs
- New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
- Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition
- Graph Classes and Forbidden Patterns on Three Vertices
- Integral mixed unit interval graphs
This page was built for publication: A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1827809)
