Carnegie Mellon University
Browse

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

Download (447.84 kB)
journal contribution
posted on 2012-12-12, 00:00 authored by Alan FriezeAlan Frieze

We describe and analyse a simple greedy algorithm 2greedy that finds a good 2-matching M in the random graph when . A 2-matching is a spanning subgraph of maximum degree two and G is drawn uniformly from graphs with vertex set , cn edges and minimum degree at least three. By good we mean that M has components. We then use this 2-matching to build a Hamilton cycle in time w.h.p.

History

Publisher Statement

This is the accepted version of the article which has been published in final form at http://dx.doi.org/10.1002/rsa.20482

Date

2012-12-12

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC