Thumbnail
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

   Open content in new tab
Source: ACM Digital Library