Details

Autor(en) / Beteiligte

• Shamir, Ron
• Tsur, Dekal

Titel

Improved algorithms for the random cluster graph model

Ist Teil von

• Random structures & algorithms, 2007-12, Vol.31 (4), p.418-449

Ort / Verlag

Hoboken: Wiley Subscription Services, Inc., A Wiley Company

Erscheinungsjahr

2007

Link zum Volltext

Quelle

Wiley Online Library (Online service)

Beschreibungen/Notizen

• We model noisy clustering data using random graphs: Clusters correspond to disjoint sets of vertices. Two vertices from the same set (resp., different sets) share an edge with probability p (resp., r < p). We give algorithms that reconstruct the clusters from the graph with high probability. Compared to previous studies, our algorithms have lower time complexity and apply under wider parameter range. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007