Ap. Punnen et Kpk. Nair, A FAST AND SIMPLE ALGORITHM FOR THE BOTTLENECK BICONNECTED SPANNING SUBGRAPH PROBLEM, Information processing letters, 50(5), 1994, pp. 283-286
Citations number
10
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
We study the problem of identifying an optimal biconnected spanning su
bgraph of an undirected graph with respect to a bottleneck objective f
unction. In a graph with m edges and n nodes, our algorithm has a wors
t-case complexity of 0(m + n log n). This improves the best available
0(m log n) bound for the problem. The min-sum version of this problem
is known to be NP-hard.