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

DOI10.1137/S0895480103430259MaRDI QIDQ5317569zbMATH OpenOpenAlexFDO

Authors 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

bipartite permutation graphsbipartite trapezoid graphscertifying algorithmsforbidden subgraph characterizationslexicographic breadth first searchproper circular arc graphs

Mathematics Subject Classification ID

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

Recommendations

• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• scientific article; zbMATH DE number 2079335
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• The LBFS structure and recognition of interval graphs
• scientific article; zbMATH DE number 6810347
• A linear time recognition algorithm for proper interval graphs
• A linear-time algorithm for proper interval graph recognition
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• scientific article; zbMATH DE number 1303554
• A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs

Cited in

(30)

• A surprising permanence of old motivations (a not-so-rigid story)
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Fully dynamic representations of interval graphs
• Unit interval vertex deletion: fewer vertices are relevant
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
• A characterization of 2-tree proper interval 3-graphs
• Fully dynamic recognition of proper circular-arc graphs
• Graphs and digraphs represented by intervals and circular arcs
• A dichotomy for minimum cost graph homomorphisms
• A simple certifying algorithm for 3-edge-connectivity
• A new representation of proper interval graphs with an application to clique-width
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. I: Theory
• Uniquely restricted matchings in interval graphs
• Bipartite permutation graphs are reconstructible
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Random Generation and Enumeration of Proper Interval Graphs
• scientific article; zbMATH DE number 2079335 (Why is no real title available?)
• Certifying algorithms
• Circularly compatible ones, D-circularity, and proper circular-arc bigraphs
• Rainbow vertex coloring bipartite graphs and chordal graphs
• Powers of cycles, powers of paths, and distance graphs
• On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency
• 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
• Certifying induced subgraphs in large graphs
• An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc 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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5317569)