Name
Abstract | ||
|---|---|---|
A 2-matching of a graph G is a spanning subgraph with maximum degree two. The size of a 2-matching U is the number of edges in U and this is at least n-(U) where n is the number of vertices of G and denotes the number of components. In this article, we analyze the performance of a greedy algorithm 2greedy for finding a large 2-matching on a random 3-regular graph. We prove that with high probability, the algorithm outputs a 2-matching U with (U) = Theta(n(1/5)). |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1002/jgt.22224 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
greedy algorithm,2-matching,random cubic graph | Graph,Spanning subgraph,Combinatorics,Vertex (geometry),Cubic graph,Greedy algorithm,Degree (graph theory),Mathematics | Journal |
Volume | Issue | ISSN |
88.0 | 3.0 | 0364-9024 |
Citations | PageRank | References |
1 | 0.36 | 11 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Deepak Bal | 1 | 35 | 7.32 |
| P BENNETT | 2 | 15 | 5.42 |
| Tom Bohman | 3 | 250 | 33.01 |
| Alan M. Frieze | 4 | 4837 | 787.00 |