Results 1 to 1 of 1
  1. #1
    kjkrum's Avatar
    kjkrum is offline Senior Member
    Join Date
    Apr 2011
    Location
    Tucson, AZ
    Posts
    1,060
    Rep Power
    6

    Default 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!

Similar Threads

  1. What is the best search algorithm for this problem?
    By daiviko in forum New To Java
    Replies: 4
    Last Post: 07-03-2012, 09:44 PM
  2. A new search algorithm by me....is it good????
    By drakula941 in forum Advanced Java
    Replies: 14
    Last Post: 11-24-2011, 06:53 AM
  3. build search tree on minimax algorithm...
    By me26 in forum Java Gaming
    Replies: 2
    Last Post: 06-29-2010, 08:24 AM
  4. Graph - Breadth First search for searching a node ?
    By JavaInLove in forum Advanced Java
    Replies: 1
    Last Post: 10-06-2008, 10:17 PM
  5. Replies: 0
    Last Post: 04-12-2008, 08:38 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •