左半边是 match, 右半边是 square
左右半图之间的连线表示 match 是否 对 square 有贡献

初始时, 把已经因为缺失 match 而不存在的 square 从图中删除

问题: 从左半图中找出最少的点, 要求这些点可以通过边到达右半图所有的点

没想到详细的解法

• 感觉这个应该是 npc (169) sunmoonstar 2006-05-16 13:39:43
  • 就是一个n-sat (0) xfxyjwf 2006-05-16 13:43:42
    • 只能 search 了 (0) sunmoonstar 2006-05-16 13:53:45
• 支配集吧 (169) frkstyc 2006-05-16 13:50:32
  • 好象是覆盖问题, 找到个介绍, 贪心是不行的, 也许可以用匹配解 (1654) sunmoonstar 2006-05-16 13:53:25
  • 恩,应该是支配集,我错了 (0) sunmoonstar 2006-05-16 13:55:11
  • 终于回归到经典模型, 基本理解 (0) sunmoonstar 2006-05-16 14:28:49
    • 但现在的问题是dominating set problem是npc (0) gniuxiao 2007-01-04 14:39:11