CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5
  1. #1
    Join Date
    Apr 2009
    Posts
    16

    Underlying Algorithm for this Graph Problem

    Hi,

    Can anyone give an hint as to what is the underlying problem for this graph problem?

    https://icpcarchive.ecs.baylor.edu/external/64/6450.pdf

    I think we need to sort the number of nodes by most edges and as we choose a node, ignore the nodes to which this selected node is connected to?

    Any hints will be appreciated.

    Thanks

  2. #2
    Join Date
    Jul 2013
    Posts
    576

    Re: Underlying Algorithm for this Graph Problem

    Quote Originally Posted by vsha041 View Post
    the underlying problem?
    I'd say it's a set cover problem.

    Associated with every user there's a set of friends (a friend-set).

    There's also the set of all users that should be reached (the target-set).

    The problem becomes, what's the smallest number of friend-sets that together as a union contains all users of the target-set or more?

    There's an efficient approximately optimal greedy algorithm for this problem:

    First select the friend-set that share the most users with the target-set. Remove these from the target-set. Then repeat this with the remaining friend-sets until the target-set is empty. It's then covered by the selected friend-sets.
    Last edited by razzle; March 3rd, 2014 at 06:48 PM.

  3. #3
    Join Date
    Apr 2009
    Posts
    16

    Re: Underlying Algorithm for this Graph Problem

    Thanks Razzle for your time and effort. This problem turns out to be NP Complete and the problem is basically Dominating Set Problem.

    http://en.wikipedia.org/wiki/Dominating_set

  4. #4
    Join Date
    Jul 2013
    Posts
    576

    Re: Underlying Algorithm for this Graph Problem

    Quote Originally Posted by vsha041 View Post
    This problem turns out to be NP Complete and the problem is basically Dominating Set Problem.
    Well, I think my formulation as a Set Cover problem is correct. In the Wikipedia entry Dominating Set is listed as related so I guess both formulations are possible.

    Set Cover is also NP-complete but it has the advantage of efficient approximate solutions (of which I mentioned one). It's almost a necessity if an NP hard algorithm is to be used in practice. I don't know the situation for Dominating Set.

    Please feel free to explain why you prefer Dominating Set?
    Last edited by razzle; March 15th, 2014 at 04:48 PM.

  5. #5
    Join Date
    Apr 2009
    Posts
    16

    Re: Underlying Algorithm for this Graph Problem

    Sorry for late reply but your answer is also right. I got my code ACCEPTED by writing brute force solution of dominating set problem.

Tags for this Thread

Posting Permissions

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





Click Here to Expand Forum to Full Width

Featured