Augmenting trees so that every three vertices lie on a cycle (Q5957303)
From MaRDI portal
scientific article; zbMATH DE number 1716685
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Augmenting trees so that every three vertices lie on a cycle |
scientific article; zbMATH DE number 1716685 |
Statements
Augmenting trees so that every three vertices lie on a cycle (English)
0 references
8 August 2002
0 references
The authors determine the minimum number of edges that must be added to a tree so that every three vertices lie on a cycle. Their proof provides an \(O(n^2)\) algorithm for finding a minimum augmenting set of edges for a tree of order \(n\).
0 references
tree
0 references
graph augmentation
0 references
cycle
0 references
3-cyclable
0 references
graph algorithm
0 references
0 references
