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

DOI10.1137/S0895480103430259zbMATH Open1069.05056OpenAlexW2032212328MaRDI QIDQ5317569FDOQ5317569

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cited In (30)

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

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)