The LBFS Structure and Recognition of Interval Graphs
From MaRDI portal
Publication:3058537
DOI10.1137/S0895480100373455zbMath1207.05131MaRDI QIDQ3058537
Stephan Olariu, Lorna K. Stewart, Derek Gordon Corneil
Publication date: 3 December 2010
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895480100373455
algorithm; recognition; chordal graphs; AT-free graphs; interval graphs; structure; lexicographic breadth first search
68R10: Graph theory (including graph drawing) in computer science
05C75: Structural characterization of families of graphs
05C85: Graph algorithms (graph-theoretic aspects)
05C62: Graph representations (geometric and intersection representations, etc.)
Related Items
Unnamed Item, The Recognition Problem of Graph Search Trees, The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs, Min-Orderable Digraphs, Star Partitions of Perfect Graphs, Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition, Unnamed Item, Recognition and drawing of stick graphs, On rectangle intersection graphs with stab number at most two, Graph Classes and Forbidden Patterns on Three Vertices, Happy set problem on subclasses of co-comparability graphs, Intersection graphs of non-crossing paths, Linearizing partial search orders, Recognizing interval bigraphs by forbidden patterns, A new LBFS-based algorithm for cocomparability graph recognition, Recognition and characterization of chronological interval digraphs, Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms, Unit and single point interval graphs, Interval graph representation with given interval and intersection lengths, Strict chordal and strict split digraphs, Extending partial representations of proper and unit interval graphs, End-vertices of LBFS of (AT-free) bigraphs, Minimal obstructions for partial representations of interval graphs, On the stab number of rectangle intersection graphs, Interval scheduling and colorful independent sets, A tie-break model for graph search, Homothetic polygons and beyond: maximal cliques in intersection graphs, A new graph parameter to measure linearity, Non-edge orientation and vertex ordering characterizations of some classes of bigraphs, A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs, Recognizing graph search trees, Happy set problem on subclasses of co-comparability graphs, Graph searches and their end vertices, Recognizing simple-triangle graphs by restricted 2-chain subgraph cover, Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review, Extending partial representations of subclasses of chordal graphs, Robinsonian matrices: recognition challenges, Extending partial representations of interval graphs, Chronological rectangle digraphs which are two-terminal series-parallel, Computing the clique-separator graph for an interval graph in linear time, On the Power of Graph Searching for Cocomparability Graphs, Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number, A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs, Uniquely Restricted Matchings in Interval Graphs
