EUVIMEDEUVIMED entdecken
Crossref

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

Deepak Bal, Patrick Bennett, Tom Bohman, Alan Frieze

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →