In this paper, we propose several new distributed algorithms for producing sets of nodes that can be used to form backbones of an ad hoc wireless network. Our focus is on producing small sets that are d-hop connected and ...