An O(nm)-time certifying algorithm for recognizing HHD-free graphs

DOI10.1016/J.TCS.2012.06.006MaRDI QIDQ714793zbMATH OpenOpenAlexFDO

Authors Stavros D. Nikolopoulos, Leonidas Palios

Publication date 11 October 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.06.006

zbMATH Keywords

certifying algorithmsHDD freeHHD-free graphshouse-, hole- or domino-freeperfectly orderable graphsrecognition

Mathematics Subject Classification ID

Graph theory (05C99) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An O(nm)-Time Certifying Algorithm for Recognizing HHD-Free Graphs
• An \(O( n^{3})\)-time recognition algorithm for hhds-free graphs
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science
• Recognizing HH-free, HHD-free, and Welsh-Powell opposition graphs

Cites work

• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithms for \(P_4\)-comparability graph recognition and acyclic \(P_4\)-transitive orientation
• An O(nm)-Time Certifying Algorithm for Recognizing HHD-Free Graphs
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• Finding houses and holes in graphs
• Graph Classes: A Survey
• scientific article; zbMATH DE number 1003286 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3891425 (Why is no real title available?)
• Introduction to algorithms
• Meyniel weakly triangulated graphs. I: Co-perfect orderability
• On brittle graphs
• On the complexity of recognizing a class of perfectly orderable graphs
• On the complexity of recognizing perfectly orderable graphs
• Recognition of some perfectly orderable graph classes
• Recognizing HH-free, HHD-free, and Welsh-Powell opposition graphs
• The strong perfect graph theorem
• Weak bipolarizable graphs

Cited in

(11)

• An \(O( n^{3})\)-time recognition algorithm for hhds-free graphs
• An O(nm)-Time Certifying Algorithm for Recognizing HHD-Free Graphs
• scientific article; zbMATH DE number 1107726 (Why is no real title available?)
• Induced embeddings into Hamming graphs
• Recognizing HH-free, HHD-free, and Welsh-Powell opposition graphs
• Graph-Theoretic Concepts in Computer Science
• On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency
• Graph-Theoretic Concepts in Computer Science
• Finding houses and holes in graphs
• Certifying induced subgraphs in large graphs
• A new characterization of HH-free graphs

This page was built for publication: An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs

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