Listing All Maximal Cliques in Large Sparse Real-World Graphs

Details Listing All Maximal Cliques in Large Sparse Real-World Graphs Listing All Maximal Cliques in Large Sparse Real-World Graphs

2011-03-02

arxiv.org/abs/1103.0318v1

Computer Science

Data Structures and Algorithms

12 pages, 4 figures. To appear at the 10th International Symposium on Experimental Algorithms (SEA 2011)

Scientific paper

We implement a new algorithm for listing all maximal cliques in sparse graphs due to Eppstein, L\"offler, and Strash (ISAAC 2010) and analyze its performance on a large corpus of real-world graphs. Our analysis shows that this algorithm is the first to offer a practical solution to listing all maximal cliques in large sparse graphs. All other theoretically-fast algorithms for sparse graphs have been shown to be significantly slower than the algorithm of Tomita et al. (Theoretical Computer Science, 2006) in practice. However, the algorithm of Tomita et al. uses an adjacency matrix, which requires too much space for large sparse graphs. Our new algorithm opens the door for fast analysis of large sparse graphs whose adjacency matrix will not fit into working memory.

Affiliated with

Also associated with

No associations

Rating

Listing All Maximal Cliques in Large Sparse Real-World Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Listing All Maximal Cliques in Large Sparse Real-World Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Listing All Maximal Cliques in Large Sparse Real-World Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-472658