Ask Your Question

Nontrivial edge cuts

asked 2021-08-15 07:19:36 +0100

guillermo gravatar image

updated 2021-08-15 11:00:54 +0100

Hi there,

I wonder how I can produce nontrivial edge cuts in a graph. An edge cut is trivial is all its edges are incident with one vertex.

The commands edge_cut and edge_connectivity tend to produce trivial cuts, even if nontrivial ones exist.

I look forward to your answer.

Regards, Guillermo

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2021-08-15 18:00:56 +0100

tmonteil gravatar image

You might have more chance by using the 'LP' algorithm that does not take care of the geometry of the graph (but we need your actual graph to check).

Another trick would be to add a very small amount of positive weight to the edges adjacent to the source and sink vertices ("very small" means that the ordering between two unequal cuts will not be modified, but the ordering between trivial cuts and other cuts with the same value will change).

edit flag offensive delete link more


Hi @tmontell,

Thank you for your comments. But I need to process a large number of graphs, and so this is impractical.

Regards, Guillermo

guillermo gravatar imageguillermo ( 2021-08-17 05:22:35 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2021-08-15 07:19:36 +0100

Seen: 164 times

Last updated: Aug 15 '21