Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Also I don't think the equivalence between edge/vertex versions is trivial at all (though maybe we just have different standards of triviality).

For example, in a grid like this:

    ..####
    .....#
    #.#..#
    #...H#
    ######
A single wall placed (i.e. vertex removed) can block two edges, and it's not obvious what graph transformation can turn that into a single edge.


You transform it into the directed case and then you turn each vertex into an arc.

There is a standard construction for going between vertex and edge cuts.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: