𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximum matchings in a class of random graphs

✍ Scribed by A.M. Frieze

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
630 KB
Volume
40
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Maximum matchings in sparse random graph
Maximum matchings in sparse random graphs: Karp–Sipser revisited
✍ Jonathan Aronson; Alan Frieze; Boris G. Pittel πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 490 KB πŸ‘ 1 views

We study the average performance of a simple greedy algorithm for finding a matching in a sparse random graph G , where c ) 0 is constant. The algorithm was first n, c r n w proposed by Karp and Sipser Proceedings of the Twenty-Second Annual IEEE Symposium on x Foundations of Computing, 1981, pp. 3

Small maximal matchings of random cubic
Small maximal matchings of random cubic graphs
✍ H. Assiyatun; W. Duckworth πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 330 KB

## Abstract We consider the expected size of a smallest maximal matching of cubic graphs. Firstly, we present a randomized greedy algorithm for finding a small maximal matching of cubic graphs. We analyze the average‐case performance of this heuristic on random __n__‐vertex cubic graphs using diffe

On large matchings and cycles in sparse
On large matchings and cycles in sparse random graphs
✍ A.M Frieze πŸ“‚ Article πŸ“… 1986 πŸ› Elsevier Science 🌐 English βš– 666 KB

Let k be a fixed positive integer. A graph H has property Mk if it contains [Β½k] edge disjoint hamilton cycles plus a further edge disjoint matching which leaves at most one vertex isolated, if k is odd. Let p = c/n, where c is a large enough constant. We show that G,,p a.s. contains a vertex induce

An Efficient Parallel Algorithm for Maxi
An Efficient Parallel Algorithm for Maximum Matching for Some Classes of Graphs
✍ I. Parfenoff πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 403 KB

The P 4 -tidy graphs were introduced by I. Rusu to generalize some already known classes of graphs with few induced P 4 (cographs, P 4 -sparse graphs, P 4 -lite graphs). Here, we propose an extension of R. Lin and S. Olariu's work (1994. J. Parallel Distributed Computing 22, 26 36.) on cographs, usi