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

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)

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)

• Powers of cycles, powers of paths, and distance graphs
• The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops
• Graphs and digraphs represented by intervals and circular arcs
• Fully dynamic recognition of proper circular-arc graphs
• A new representation of proper interval graphs with an application to clique-width
• Unit interval vertex deletion: fewer vertices are relevant
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. I: Theory
• 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
• Certifying algorithms
• A characterization of 2-tree proper interval 3-graphs
• On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency
• A surprising permanence of old motivations (a not-so-rigid story)
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• A simple certifying algorithm for 3-edge-connectivity
• scientific article; zbMATH DE number 2079335 (Why is no real title available?)
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Bipartite permutation graphs are reconstructible
• Fully dynamic representations of interval graphs
• A dichotomy for minimum cost graph homomorphisms
• Circularly compatible ones, \(D\)-circularity, and proper circular-arc bigraphs

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)