graph problems

minton3 · Post by **minton3** » Fri Sep 01, 2006 6:04 pm

HI!
My first problem is to know if a graph is bipartite in the fastest way.
I don't know any algorithm in particular to do it...and I think I can do it in the best way in O(n), or I hope so, but if someone knows a method or a good algorithm it would be nice to know it.
The second problem is this:
I have 1 graph, and I want to divide it in 2 diferent groups of nodes, in such a way that the amount of conected nodes between the first group and the second is maximum... I hope you understand my bad description.
In another way to see this problem, just think in a group of people where some of them are friends. And I want to divide it in 2 teams such that the amount of pairs of friends between 1 team and another is maximum.
I would appreciate any help!

chrismoh · Post by **chrismoh** » Fri Sep 01, 2006 7:13 pm

Checking if a graph is bipartite is basically checking if a graph can be 2-colored.

This can be done with DFS in linear time.

I'm not really sure what your second problem is, but it sounds like the Maximum Cut problem which is NP-hard.

A simple 2-approximation heuristic is simply to assign nodes in an arbitrary order, and each time assign a node to the side with which he forms the most pairs with the other side.

minton3 · Post by **minton3** » Tue Sep 05, 2006 3:02 am

Checking if a graph is bipartite is basically checking if a graph can be 2-colored.

This can be done with DFS in linear time.

thanks
But can you explain me a little more please?
I am not sure how to do it in linear time

chrismoh · Post by **chrismoh** » Tue Sep 05, 2006 3:53 am

Color every node using DFS as "black" or "white".

Color the root black, make it the current node, and do the following:

Code: Select all

For every node connected to the current node
  If node is uncolored
    Color it with the opposite color of the current node
    Recursively do a DFS on it
  Else If node is colored the same color as the current node
    Graph is not Bipartite
    exit

If an adjacency list representation is used, the running time is O(V+E) which is linear in the number of vertices and edges.

minton3 · Post by **minton3** » Tue Sep 05, 2006 6:14 am

thanks a lot for your help
it was very useful

DP · Post by DP » Tue Sep 05, 2006 9:27 pm

Hi,
How to solve the 10505(Montesco vs Capuleto)?
Is it the Bi-coloring problem? and can be done with DFS in linear time?

thnx

Hadi · Post by **Hadi** » Fri Sep 08, 2006 9:18 pm

You are right, 10505 is a bi-coloring problem, and it can be solved using a dfs in linear time