Light graphs with small routing cost
Bang Ye Wu, Kun‐Mao Chao, Chuan Yi Tang · Networks · 2002
Abstract Let G = ({1,…, n}, E, w) be an undirected graph with nonnegative edge weights w and let aij be the nonnegative requirement between vertices i and j. For any spanning subgraph H of G, the weight of H is the total weight of its edges and the routing cost of H is Σi