A FAST AND SIMPLE ALGORITHM FOR THE BOTTLENECK BICONNECTED SPANNING SUBGRAPH PROBLEM

Authors
PUNNEN AP NAIR KPK
Citation
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
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
50
Issue
5
Year of publication
1994
Pages
283 - 286
Database
ISI
SICI code
0020-0190(1994)50:5<283:AFASAF>2.0.ZU;2-T
Abstract
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.