Recognizing brittle graphs: Remarks on a paper of Hoàng and Khouzam (Q1814095)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Recognizing brittle graphs: Remarks on a paper of Hoàng and Khouzam |
scientific article; zbMATH DE number 10057
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Recognizing brittle graphs: Remarks on a paper of Hoàng and Khouzam |
scientific article; zbMATH DE number 10057 |
Statements
Recognizing brittle graphs: Remarks on a paper of Hoàng and Khouzam (English)
0 references
25 June 1992
0 references
The paper studies a subclass of perfectly-orderable graphs known as brittle graphs that can be recognized and given a perfect ordering in polynomial time. It points out that for a brittle graph of \(n\) vertices and \(m\) edges, an \(O(n^ 2m)\) time recognition algorithm can be derived from Chvátal's original definition, and also gives a more complicated \(O(m^ 2)\) time recognition algorithm.
0 references
perfect ordering
0 references
brittle graphs
0 references
0 references
0.85092646
0 references
0.84964156
0 references
0.84626144
0 references
0.8453264
0 references
0.8432975
0 references
0.84291875
0 references
