Small maximal matchings in random graphs.

DOI10.1016/S0304-3975(02)00653-9zbMath1044.68138MaRDI QIDQ1401316

Michele Zito

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

random \(d\)-regular graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (11)

Global forcing number for maximal matchings in corona products ⋮ Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks ⋮ Smallest maximal matchings of graphs ⋮ Cycle Saturation in Random Graphs ⋮ Tight concentration of star saturation number in random graphs ⋮ Star saturation number of random graphs ⋮ Saturation number of lattice animals ⋮ The cook-book approach to the differential equation method ⋮ Saturation number of fullerene graphs ⋮ The maximum fuzzy weighted matching models and hybrid genetic algorithm ⋮ Maximal matchings in polyspiro and benzenoid chains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved upper bound on the non-3-colourability threshold
• On the independence number of random graphs
• Differential equations for random processes and random graphs
• Edge Dominating Sets in Graphs
• On colouring random graphs
• An Analysis of the Greedy Heuristic for Independence Systems
• Approximating the unsatisfiability threshold of random formulas
• Paths, Trees, and Flowers
• On the existence of a factor of degree one of a connected random graph
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Small maximal matchings in random graphs.