## Abstract

The full-degree spanning tree problem is defined as follows: Given a connected graph G = (V, E), find a spanning tree T to maximize the number of vertices whose degree in T is the same as in G (these are called vertices of "full" degree). This problem is NP-hard. We present almost-optimal approximation algorithms for it assuming that coR ≠ NP. For the case of general graphs, our approximation factor is Θ(√n). Using Håstad's result on the hardness of an approximating clique, we can show that if there is a polynomial time approximation algorithm for our problem with a factor of O(n^{1/2-∈}) then coR = NP. Additionally, we present two algorithms for optimally solving small instances of the general problem and experimental results comparing our algorithm to the optimal solution and the previous heuristic used for this problem.

Original language | English (US) |
---|---|

Pages (from-to) | 203-209 |

Number of pages | 7 |

Journal | Networks |

Volume | 36 |

Issue number | 4 |

DOIs | |

State | Published - Dec 2000 |

## Keywords

- Algorithm
- Approximation
- Full degree
- Graph
- NP-hardness
- Spanning tree

## ASJC Scopus subject areas

- Information Systems
- Computer Networks and Communications