Approximation algorithms for finding low-degree subgraphs (2004)
Philip N. Klein, Radha Krishnan, Balaji Raghavachari, R. Ravi
We give quasipolynomial-time approximation algorithms for designing networks with a minimum degree. Using our methods, one can design networks whose connectivity is specified by “proper ”...
The directed minimum-degree spanning tree problem (2001)
Radha Krishnan, Balaji Raghavachari
Abstract. Consider a directed graph G =(V,E) with n vertices and a root vertex r ∈ V. The DMDST problem for G is one of constructing a spanning tree rooted at r, whose maximal degree is the...