Generating Random Graphs with Large Girth

Details Generating Random Graphs with Large Girth Generating Random Graphs with Large Girth

2008-11-18

arxiv.org/abs/0811.2853v1

Computer Science

Data Structures and Algorithms

10 pages, Procedings of SODA 2009, New York January 2009

Scientific paper

We present a simple and efficient algorithm for randomly generating simple graphs without small cycles. These graphs can be used to design high performance Low-Density Parity -Check (LDPC) codes. For any constant k, alpha<1/2k(k+3) and m=O(n^{1+alpha}), our algorithm generate s an asymptotically uniform random graph with n vertices, m edges, and girth larger tha n k in polynomial time. To the best of our knowledge this is the first polynomial-algorith m for the problem. Our algorithm generates a graph by sequentially adding m edges to an empty graph with n vertices. Recently, these types of sequential methods for counting and random generation have been very successful.

Affiliated with

Also associated with

No associations

Rating

Generating Random Graphs with Large Girth 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 Generating Random Graphs with Large Girth, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generating Random Graphs with Large Girth will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-100731