Classifying customer-provider relationships in the internet
Thomas Erlebach, Alexander Hall, Thomas Schank · Repository for Publications and Research Data (ETH Zurich) · 2002
The problem of inferring customer-provider relationships in the autonomous system topology of the Internet leads to the following optimization problem: given an undirected graph G and a set P of paths in G, orient the edges of G such that as many paths as possible are valid, meaning that they do not contain an internal node with both incident edges on the path directed away from that node. The complexity of this problem was left open by Subramanian et al. ("Characterizing the Internet hierarchy from multiple vantage points," INFOCOM 2002). We show