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

Bal Deepak | Zendy; Bennett Patrick | Zendy; Bohman Tom | Zendy; Frieze Alan | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

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

Author(s) -

Bal Deepak,

Bennett Patrick,

Bohman Tom,

Frieze Alan

Publication year - 2018

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.22224

Subject(s) - combinatorics , mathematics , factor critical graph , matching (statistics) , graph factorization , greedy algorithm , graph , random graph , discrete mathematics , line graph , algorithm , graph power , statistics

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research