A greedy algorithm for finding a large 2‐matching on a random cubic graph
Journal of Graph Theory · 2018-07 · 88 (3) · 449-481
DOI: 10.1002/jgt.22224 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 27.11.2017. Verfasst von Deepak Bal und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 18 Literaturangaben. Gefördert von: National Science Foundation, Simons Foundation.
Abstract (Originalsprache)
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 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 .
Förderung
- National Science Foundation
- Simons Foundation
Zitieren
APA
Bal, D., Bennett, P., Bohman, T., & Frieze, A. (2018). A greedy algorithm for finding a large 2‐matching on a random cubic graph. Journal of Graph Theory, 88(3), 449-481. https://doi.org/10.1002/jgt.22224
Vancouver
Bal D, Bennett P, Bohman T, Frieze A. A greedy algorithm for finding a large 2‐matching on a random cubic graph. Journal of Graph Theory. 2018;88(3):449-481. doi:10.1002/jgt.22224
BibTeX
@article{Bal2018,
author = {Bal, Deepak and Bennett, Patrick and Bohman, Tom and Frieze, Alan},
title = {A greedy algorithm for finding a large 2‐matching on a random cubic graph},
journal = {Journal of Graph Theory},
year = {2018},
volume = {88},
number = {3},
pages = {449--481},
doi = {10.1002/jgt.22224}
}
EUVIMED