※ 引述《DJWS (...)》之銘言：
: 推 FRAXIS: 題目要求是不是要找一個maximal matching?
: 這題跟極大沒有關係。
: 再者，最小邊支配集 != 最大邊獨立集(最大匹配)。
: 除非這題的圖是某種特殊圖類，剛好滿足你說的那樣。這部分我不清楚。
其實 minimum edge dominating set 的大小是跟
minimum independent edge dominating set 是一樣的
然後 minimum independent edge dominating set 是一個
minimum maximal matching
http://cgi.di.uoa.gr/~vassilis/co/dominating-sets.pdf
當然，minimum maximal matching也不好找就是了，
而且當圖是有weighted的時候，這關係就不存在了。
: → dreamoon: 若把邊當點，大概可以應轉成一般圖的最大獨立集
: 最小邊支配集 != 最大邊獨立集(最大匹配)。
: -----------
: 結論就是不要再肖想獨立集了，除非那是一種特殊的圖類。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.149
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1421342314.A.318.html