Results 1 to 1 of 1
- 07-14-2012, 01:17 PM #1
In search of a graph algorithm...
I have only a basic knowledge of graph theory and even less of set theory, so I hope I can accurately describe what I want to do.
In graph theory, a cut-vertex is a vertex which, when removed from a graph, increases the number of connected components in the graph. I'm looking for a way to find minimal sets of up to n vertices which have the property that when all members of the set are removed from the graph, the number of connected components in the graph is increased.
I have an idea, but it might be naive. I'm thinking I could perform a breadth-first search from each vertex of the graph, and then find the shortest paths from the original vertex to every other vertex. These paths would be sets of integers, with each integer identifying a vertex. Call the set containing these sets of integers A. The problem would then be to identify a set B containing n or fewer integers such that the intersection of B with every set in A is non-empty.
Last edited by kjkrum; 07-14-2012 at 01:22 PM.Get in the habit of using standard Java naming conventions!
- By daiviko in forum New To JavaReplies: 4Last Post: 07-03-2012, 09:44 PM
- By drakula941 in forum Advanced JavaReplies: 14Last Post: 11-24-2011, 06:53 AM
- By me26 in forum Java GamingReplies: 2Last Post: 06-29-2010, 08:24 AM
- By JavaInLove in forum Advanced JavaReplies: 1Last Post: 10-06-2008, 10:17 PM
- By Java Tip in forum java.langReplies: 0Last Post: 04-12-2008, 08:38 PM