  The rapid growth of wireless and mobile Internet has led to wide applications
of exchanging resources over network, in which how to fairly allocate resources
has become a critical challenge. To motivate sharing, a BD Mechanism is
proposed for resource allocation, which is based on a combinatorial structure
called bottleneck decomposition. The mechanism has been shown with properties
of fairness, economic efficiency [17], and truthfulness against two kinds of
strategic behaviors [2,3]. Unfortunately, the crux on how to compute a
bottleneck decomposition of any graph is remain untouched. In this paper, we
focus on the computation of bottleneck decomposition to fill the blanks and
prove that the bottleneck decomposition of a network $G = (V, E; w_v)$ can be
computed in $O(n^6 log(nU))$, where $n = |V|$ and $U = max_{v\in V} w_v$. Based
on the bottleneck decomposition, a fair allocation in resource exchange system
can be obtained in polynomial time. In addition, our work completes the
computation of a market equilibrium and its relationship to two concepts of
fairness in resource exchange.
