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

Deepak Bal, Patrick Bennett, Tom Bohman, Alan Frieze

Research output: Contribution to journalArticleResearchpeer-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)=Θ(n1/5).

Original languageEnglish
Pages (from-to)449-481
Number of pages33
JournalJournal of Graph Theory
Volume88
Issue number3
DOIs
StatePublished - 1 Jul 2018

Fingerprint

Cubic Graph
Greedy Algorithm
Random Graphs
Spanning Subgraph
Number of Components
Regular Graph
Maximum Degree
Denote
Output
Graph in graph theory

Keywords

  • 2-matching
  • greedy algorithm
  • random cubic graph

Cite this

Bal, Deepak ; Bennett, Patrick ; Bohman, Tom ; Frieze, Alan. / A greedy algorithm for finding a large 2-matching on a random cubic graph. In: Journal of Graph Theory. 2018 ; Vol. 88, No. 3. pp. 449-481.
@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",
year = "2018",
month = "7",
day = "1",
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",

}

A greedy algorithm for finding a large 2-matching on a random cubic graph. / Bal, Deepak; Bennett, Patrick; Bohman, Tom; Frieze, Alan.

In: Journal of Graph Theory, Vol. 88, No. 3, 01.07.2018, p. 449-481.

Research output: Contribution to journalArticleResearchpeer-review

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/1

Y1 - 2018/7/1

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 - http://www.scopus.com/inward/record.url?scp=85046889991&partnerID=8YFLogxK

U2 - 10.1002/jgt.22224

DO - 10.1002/jgt.22224

M3 - Article

VL - 88

SP - 449

EP - 481

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 3

ER -