how to find all cut vertexes in a given graph ??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
This problem is taken from www.codeforces.com.What can be the possible
approaches??
A smile house is created to raise the mood. It has *n* rooms. Some of the
rooms are connected by doors. For each two rooms (number *i*and *j*), which
are connected by a door, Petya knows their value *c**ij* —
Consider each person as a node on a graph. Two nodes are connected only when
both persons like each other.
Now do any traversal of this graph to find the number of connected
components. That should be the minimum no. of houses required.
On Sun, May 29, 2011 at 9:17 PM, ross
There are n persons.
You are provided with a list of ppl which each person does not like.
Determine the minm no. of houses required such that, in no house
2 people should dislike each other.
Is there a polynomial time solution exist for this? Or is this not
solvable at all?
--
You received this
it is exactly a graph coloring problem. so it has no polynomial order
solution.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
On 11/30/07, John [EMAIL PROTECTED] wrote:
Given a DAG and two vertices s and t , give a linear time number of
paths between s and t in G.
How does topological sort help in finding the same ?
Hi Joh,
you can do a dynamic programming algorithm Your state is S[x] = number
of path going from s
Just to clarify, you are looking for a linear time algorithm that
counts all s-t paths (not necessarily disjoint) in a DAG?
On Nov 29, 10:35 pm, John [EMAIL PROTECTED] wrote:
Given a DAG and two vertices s and t , give a linear time number of
paths between s and t in G.
How does topological
Just use BFS, its running time is O(V+E). In our case, there's no cycle
in DAG so, E=V-1 always.
John wrote:
Given a DAG and two vertices s and t , give a linear time number of
paths between s and t in G.
How does topological sort help in finding the same ?
Not sure about what's wrong with your code is but the answer to the
problem is Warshall's algorithm for graph closure.
Just to brief, say we are given the adjacency matrix A[1] where A[1][i]
[j] = 1 if there's an edge from i to j.
Let A[k][i][j] be the the number of paths from i to j passing
Here's the code.
void Closure(int **a, int v) //a is the given adjacency matrix and v
is the number of vertices
{
int **t1 = new int*[v];
int **t2 = new int*[v];
for(int i = 0; i v; ++i)
{
t1[i] = new int[v];
t2[i] = new int[v];
Can it be a solution?
At first let us think all the edges are undirected. That is if a adjacent to
b then both a-b and b-a are present. then we discard a-b if a is the
current vertex with maximum outdegree and b is its adjacent with minimum
outdegree and b-a is present
we continue it again and
Ohh, sorry to have missed that information. Consider minimizing the
maximum out-degree.
On May 16, 5:04 pm, Rajiv Mathews [EMAIL PROTECTED] wrote:
Could you please explain the question.
Typically in a directed graph we talk of in-degree and out-degree for
a vertex. So is the question then
Could you please explain the question.
Typically in a directed graph we talk of in-degree and out-degree for
a vertex. So is the question then to minimize the maximum of these in
all vertices of the graph? If so what operations are permitted?
On 5/16/07, pramod [EMAIL PROTECTED] wrote:
Here's
Hello!
We have a graph that is not directional. We want an algorithm to find
out if this graph is divided to two parts or not.
mofid
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post
14 matches
Mail list logo
