A greedy algorithm for finding a large 2-matching on a random cubic graph

Deepak Bal; Patrick Bennett; Tom Bohman; Alan Frieze

doi:10.1002/jgt.22224

A greedy algorithm for finding a large 2-matching on a random cubic graph

Deepak Bal, Patrick Bennett, Tom Bohman, Alan Frieze

Mathematics

Research output: Contribution to journal › Article › peer-review

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-k(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 k(U)=Θ(n^1/5).

Original language	English
Pages (from-to)	449-481
Number of pages	33
Journal	Journal of Graph Theory
Volume	88
Issue number	3
DOIs	https://doi.org/10.1002/jgt.22224
State	Published - Jul 2018

Keywords

2-matching
greedy algorithm
random cubic graph

Access to Document

10.1002/jgt.22224

Cite this

@article{ee4af530a4c4415984a0f54860c08e3a,

title = "A greedy algorithm for finding a large 2-matching on a random cubic graph",

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-k(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 k(U)=Θ(n1/5).",

keywords = "2-matching, greedy algorithm, random cubic graph",

author = "Deepak Bal and Patrick Bennett and Tom Bohman and Alan Frieze",

note = "Publisher Copyright: {\textcopyright} 2017 Wiley Periodicals, Inc.",

year = "2018",

month = jul,

doi = "10.1002/jgt.22224",

language = "English",

volume = "88",

pages = "449--481",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}

TY - JOUR

T1 - A greedy algorithm for finding a large 2-matching on a random cubic graph

AU - Bal, Deepak

AU - Bennett, Patrick

AU - Bohman, Tom

AU - Frieze, Alan

PY - 2018/7

Y1 - 2018/7

N2 - 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-k(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 k(U)=Θ(n1/5).

AB - 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-k(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 k(U)=Θ(n1/5).

KW - 2-matching

KW - greedy algorithm

KW - random cubic graph

UR - https://www.scopus.com/pages/publications/85046889991

U2 - 10.1002/jgt.22224

DO - 10.1002/jgt.22224

M3 - Article

AN - SCOPUS:85046889991

SN - 0364-9024

VL - 88

SP - 449

EP - 481

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 3

ER -

A greedy algorithm for finding a large 2-matching on a random cubic graph

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this