tag:blogger.com,1999:blog-29632375.post2890868989972301886..comments2023-06-19T19:45:40.281-07:00Comments on vexorian's blog: SRM 594 editorial (Part 1)Unknownnoreply@blogger.comBlogger2125tag:blogger.com,1999:blog-29632375.post-84784359543067940742013-10-21T08:08:40.971-07:002013-10-21T08:08:40.971-07:00I view the general version of this problem as:
1)...I view the general version of this problem as: <br />1) You have two disjoint sets of elements (here they are blank spaces + blank spaces created by removing white tokens)<br />2) You want to maximize the total number of elements you have in both sets in your solution<br />3) There exist constraints between the two sets which state that if one element is present, some other node cannot be present (represented as edges).<br /><br /><br />Starting with all vertices present (the ideal solution), what is the minimum number of vertices you need to remove to have all constraints met? Then it is clear to me that the solution is total elements - minimum vertex cover.<br /><br /><br />I would have to guess the writer used BPM just because it is == min vertex cover. I can't think of a way to conceptualize it with BPM that "makes sense."JOmegaCVnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-11479330524187613842013-10-19T10:35:20.440-07:002013-10-19T10:35:20.440-07:00D1-550 is not yet clear to me even after reading t...D1-550 is not yet clear to me even after reading that long explanation. It confused me first why subtracting 'max'flow maximizes what we want. But it should be thought really as 'min'cut or even better #('.'s and 'o's) - 'min'vertex-cover, which somewhat makes sense. I know its really hard to write editorial for such problems. But, I wonder if the writer who thought of this problem in the first place could have contributed to editorial to make understanding better. Thanks for all your write ups, really appreciate and enjoy them !Vijaynoreply@blogger.com