Cluster graph modification problems

By Ron Shamir, Roded Sharan, Dekel Tsur. Discrete Applied Mathematics, 2002

386 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/3cb8b3efa6dd1a7b163066f83a9fcbe1f84695ab

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Venkatesan Guruswami
2. Ron Shamir
3. Moses Charikar
4. Ping Li
5. Brian Kulis
6. Anshumali Shrivastava
7. Jia Deng
8. Mohammad Norouzi

In Molecular Biology

1. Ron Shamir
2. Roded Sharan
3. Adi Maron-Katz
4. Igor Ulitsky
5. Trey Ideker
6. Olaf Sporns
7. Bonnie Berger

Citations in the corpus

• CLICK and EXPANDER: a system for clustering and visualizing gene expression data (2003, background): “This problem is NPhard even for a complete graph with edge weights 1 or −1 only (Shamir et al., 2002).”
• Clustering with qualitative information (2003, background): “[3] studied the computational complexity of the problem and showed that MaxAgree (and hence also MinDisAgree) is NP-hard for complete graphs.”