graph problems

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
minton3
New poster
Posts: 3
Joined: Fri Sep 01, 2006 5:36 pm

graph problems

Post by minton3 »

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
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA

Post by chrismoh »

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
New poster
Posts: 3
Joined: Fri Sep 01, 2006 5:36 pm

Post by minton3 »

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
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA

Post by chrismoh »

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
New poster
Posts: 3
Joined: Fri Sep 01, 2006 5:36 pm

Post by minton3 »

thanks a lot for your help
it was very useful

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP »

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
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi »

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

Post Reply

Return to “Algorithms”