Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs

DOI10.1137/S0895480103430259zbMath1069.05056OpenAlexW2032212328MaRDI QIDQ5317569

Jing Huang, Pavol Hell

Publication date: 16 September 2005

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480103430259

zbMATH Keywords

certifying algorithmsforbidden subgraph characterizationslexicographic breadth first searchbipartite permutation graphsproper circular arc graphsbipartite trapezoid graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (28)

On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency ⋮ BIPARTITE PERMUTATION GRAPHS ARE RECONSTRUCTIBLE ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs ⋮ A dichotomy for minimum cost graph homomorphisms ⋮ A simple certifying algorithm for 3-edge-connectivity ⋮ Fully dynamic representations of interval graphs ⋮ Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory ⋮ Certifying algorithms ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs ⋮ Unit interval vertex deletion: fewer vertices are relevant ⋮ A characterization of 2-tree proper interval 3-graphs ⋮ Powers of cycles, powers of paths, and distance graphs ⋮ Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs ⋮ The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops ⋮ An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ Random Generation and Enumeration of Proper Interval Graphs ⋮ A Lex-BFS-based recognition algorithm for Robinsonian matrices ⋮ Circularly Compatible Ones, $D$-Circularity, and Proper Circular-Arc Bigraphs ⋮ A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs ⋮ A new representation of proper interval graphs with an application to clique-width ⋮ A surprising permanence of old motivations (a not-so-rigid story) ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ Uniquely Restricted Matchings in Interval Graphs ⋮ Fully dynamic recognition of proper circular-arc graphs ⋮ Graphs and digraphs represented by intervals and circular arcs

This page was built for publication: Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs