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

DOI10.1016/j.tcs.2012.06.006zbMath1251.05173OpenAlexW2003077878MaRDI QIDQ714793

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

recognitionperfectly orderable graphscertifying algorithmsHDD freeHHD-free graphshouse-, hole- or domino-free

Mathematics Subject Classification ID

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

Related Items (2)

On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency ⋮ Induced Embeddings into Hamming Graphs.

Cites Work

• Meyniel weakly triangulated graphs. I: Co-perfect orderability
• The strong perfect graph theorem
• On the complexity of recognizing perfectly orderable graphs
• Weak bipolarizable graphs
• Recognition of some perfectly orderable graph classes
• Algorithms for \(P_4\)-comparability graph recognition and acyclic \(P_4\)-transitive orientation
• On the complexity of recognizing a class of perfectly orderable graphs
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• An O(nm)-Time Certifying Algorithm for Recognizing HHD-Free Graphs
• On brittle graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• Finding houses and holes in graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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