首页> 外文会议>Discrete Geometry, Combinatorics and Graph Theory; Lecture Notes in Computer Science; 4381 >Sufficient Conditions for the Existence of Perfect Heterochromatic Matchings in Colored Graphs
【24h】

Sufficient Conditions for the Existence of Perfect Heterochromatic Matchings in Colored Graphs

机译:彩色图中存在完美异色匹配的充分条件

获取原文
获取原文并翻译 | 示例

摘要

Let G = (V, E) be an edge-colored graph. A matching of G is called heterochromatic if its any two edges have different colors. Unlike uncolored matchings for which the maximum matching problem is solvable in polynomial time, the maximum heterochromatic matching problem is NP-complete. This means that to find both sufficient and necessary good conditions for the existence of perfect heterochromatic matchings should be not easy. In this paper, we obtain sufficient conditions of Hall-type and Tutte-type for the existence of perfect heterochromatic matchings in colored bipartite graphs and general colored graphs. We also obtain a sufficient and necessary condition of Berge-type to verify if a heterochromatic matching M of G is maximum.
机译:令G =(V,E)为边色图。如果G的任何两个边缘具有不同的颜色,则将其匹配称为异色。与无色匹配不同,无色匹配在多项式时间内可以解决最大匹配问题,而最大异色匹配问题是NP完全的。这意味着要为存在完美的异色匹配找到充分和必要的良好条件并不容易。在本文中,我们获得了霍尔型和Tutte型的充分条件,以便在彩色二分图和一般彩色图中存在完美的异色匹配。我们还获得了Berge型的充分必要条件,以验证G的异色匹配M是否最大。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号