### Finding minimum congestion spanning treesFinding minimum congestion spanning trees

Access Restriction
Subscribed

 Author Werneck, Renato ♦ Setubal, Joo ♦ da Conceico, Arlindo Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2000 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Abstract Given a weighted graph G = (V, E), a positive integer $\textit{k},$ and a penalty function $\textit{wp},$ we want to find $\textit{k}$ spanning trees on $\textit{G},$ not necessarily disjoint, of minimum total weight, such that the weight of each edge is subject to a penalty given by $\textit{wp}$ if it belongs to more than one tree. The objective function to be minimized is $Σ\textit{e∈EWe(ie)},$ where $\textit{ie}$ is the number of times edge e appears in the solution and We(ie) = iewp(e, ie) is the aggregate cost of using edge e ie times. For the case when $\textit{We}$ is weakly convex, which should have wide application in congestion problems, we present a polynomial time algorithm; the algorithm's complexity is quadratic in $\textit{k}.$ We also present two heuristics with complexity linear in $\textit{k}.$ In an experimental study we show that these heuristics are much faster than the exact algorithm also in practice. These experiments present a diverse combination of input families (four), varying $\textit{k}$ (up to 1000), and penalty functions (two). In most inputs tested the solutions given by the heuristics were within 1% of optimal or much better, especially for large $\textit{k}.$ The worst quality observed was 3.2% of optimal. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2000-12-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 5

#### Open content in new tab

Source: ACM Digital Library