A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem (Q2656175)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem |
scientific article |
Statements
A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem (English)
0 references
10 March 2021
0 references
The problem is to find a spanning tree with maximal number of internal vertices in an undirected graph. It seems to have already earlier attracted some activity. Here, a 7-line verbally formulated algorithm is presented. It is based on a sequence of ideas to reduce the given graph. Performance ratios of \(\frac{4}{3}\) vs. \(\frac{3}{2}\) and others in the literature are discussed.
0 references
maximum internal spanning tree problem
0 references
approximation algorithm
0 references
performance ratio
0 references
0 references
0 references
0 references
