An O( n^3)-time recognition algorithm for hhds-free graphs

DOI10.1007/S00373-007-0706-3MaRDI QIDQ2373437zbMATH OpenOpenAlexFDO

Authors Elaine M. Eschen, Chính T. Hoàng, R. Sritharan

Publication date 19 July 2007

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-007-0706-3

zbMATH Keywords

GraphRecognition algorithmhhds-freePerfectly orderable

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Recommendations

• An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs
• An O(nm)-Time Certifying Algorithm for Recognizing HHD-Free Graphs
• Graph-Theoretic Concepts in Computer Science
• An \(O(n^ 3)\) recognition algorithm for bithreshold graphs
• Recognizing HH-free, HHD-free, and Welsh-Powell opposition graphs
• An \(O(n^3)\) time algorithm for recognizing threshold dimension 2 graphs
• Graph-Theoretic Concepts in Computer Science
• A new characterization of HH-free graphs
• A faster algorithm to recognize even-hole-free graphs
• A faster algorithm to recognize even-hole-free graphs

Cites work

• Algorithmic Aspects of Vertex Elimination on Graphs
• Characterizations of strongly chordal graphs
• Doubly Lexical Orderings of Matrices
• Finding houses and holes in graphs
• Graph Classes: A Survey
• Graph-Theoretic Concepts in Computer Science
• On brittle graphs
• On rigid circuit graphs
• On the complexity of recognizing perfectly orderable graphs
• On the semi-perfect elimination
• Recognizing HH-free, HHD-free, and Welsh-Powell opposition graphs

Cited in

(6)

• An O(nm)-Time Certifying Algorithm for Recognizing HHD-Free Graphs
• An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs
• Graph-Theoretic Concepts in Computer Science
• Finding a sun in building-free graphs
• Graph-Theoretic Concepts in Computer Science
• Recognizing HH-free, HHD-free, and Welsh-Powell opposition graphs

This page was built for publication: An \(O( n^{3})\)-time recognition algorithm for hhds-free graphs

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