Research Findings from University of Illinois Update Understanding of Algorithms

摘要

"Given an undirected graph G with edge costs and a specified set of terminals, let the density of any nsubgraph be the ratio of its cost to the number of terminals it contains. If G is 2-connected, does it contain nsmaller 2-connected subgraphs of density comparable to that of G' We answer this question in the naffirmative by giving an algorithm to pruneG and find such subgraphs of any desired size, incurring only a nlogarithmic factor increase in density (plus a small additive term)," scientists writing in the journal nAlgorithmica report.