| Article ID: | iaor20011488 |
| Country: | Netherlands |
| Volume: | 23 |
| Issue: | 1/2 |
| Start Page Number: | 21 |
| End Page Number: | 26 |
| Publication Date: | Aug 1998 |
| Journal: | Operations Research Letters |
| Authors: | Dahl Geir |
| Keywords: | computational analysis |
A spanning tree in a graph G where each node has distance at most 2 from a root node r is called a 2-hop spanning tree. For given edge weights the 2-hop spanning tree problem is to find a minimum weight 2-hop spanning tree. The problem is NP-hard. We study the problem from a polyhedral point of view based on a directed formulation and give, for example, a completeness result when G is an n-wheel.