On a Greedy 2-Matching Algorithm and Hamilton Cycles in Random Graphs with Minimum Degree at Least Three

Details On a Greedy 2-Matching Algorithm and Hamilton Cycles in Random Graphs with Minimum Degree at Least Three On a Greedy 2-Matching Algorithm and Hamilton Cycles in Random Graphs with Minimum Degree at Least Three

2011-07-25

arxiv.org/abs/1107.4947v3

Mathematics

Combinatorics

Companion paper to "On a sparse random graph with minimum degree {three}: Likely Posa's sets are large"

Scientific paper

We describe and analyse a simple greedy algorithm \2G\ that finds a good 2-matching $M$ in the random graph $G=G_{n,cn}^{\d\geq 3}$ when $c\geq 15$. A 2-matching is a spanning subgraph of maximum degree two and $G$ is drawn uniformly from graphs with vertex set $[n]$, $cn$ edges and minimum degree at least three. By good we mean that $M$ has $O(\log n)$ components. We then use this 2-matching to build a Hamilton cycle in $O(n^{1.5+o(1)})$ time \whp.

Affiliated with

Also associated with

No associations

Rating

On a Greedy 2-Matching Algorithm and Hamilton Cycles in Random Graphs with Minimum Degree at Least Three 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 On a Greedy 2-Matching Algorithm and Hamilton Cycles in Random Graphs with Minimum Degree at Least Three, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On a Greedy 2-Matching Algorithm and Hamilton Cycles in Random Graphs with Minimum Degree at Least Three will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-572623