Scholarlink

We consider the problem of finding a large rainbow matching in a random graph with randomly colored edges. In particular we analyze the performance of two greedy algorithms for this problem. The algorithms we study are colored versions of algorithms that were previously used to find large matchings in random graphs (i.e., the color-free version of our present problem).

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Rainbow Greedy Matching Algorithms

  • 章节

  • 发表日期：

    2025年

查看全文
  • Patrick Bennett,
  • Colin Cooper,
  • Alan Frieze

摘要

We consider the problem of finding a large rainbow matching in a random graph with randomly colored edges. In particular we analyze the performance of two greedy algorithms for this problem. The algorithms we study are colored versions of algorithms that were previously used to find large matchings in random graphs (i.e., the color-free version of our present problem).