Ah. I understand now. Thanks.
Dave
On Sep 13, 2:28 pm, sirpi wrote:
> On Sep 13, 7:27 pm, Dave wrote:
>
> > Suppose the graph consists of three nodes in a triangle. You number
> > your starting node at level 1 and the other two at level 2. How do you
> > proceed?
>
> If the three nodes are a
On Sep 13, 7:27 pm, Dave wrote:
> Suppose the graph consists of three nodes in a triangle. You number
> your starting node at level 1 and the other two at level 2. How do you
> proceed?
If the three nodes are a triangle then in a *depth* search, there is
node 1 and one of the neighbors is
@Dave : DFS doesnt work that way. you might like to brush up tree
traversal :D
_dufus
On Sep 13, 10:27 pm, Dave wrote:
> Suppose the graph consists of three nodes in a triangle. You number
> your starting node at level 1 and the other two at level 2. How do you
> proceed?
>
> Dave
>
> On Sep
Suppose the graph consists of three nodes in a triangle. You number
your starting node at level 1 and the other two at level 2. How do you
proceed?
Dave
On Sep 12, 9:27 pm, Gene wrote:
> On Sep 6, 5:28 am, ankur aggarwal wrote:
>
> > google question : find triangle in a graph Given an undirec
@Gene : Smooth :)
How did I miss such an elegant solution..Duh
_dufus
On Sep 13, 7:27 am, Gene wrote:
> On Sep 6, 5:28 am, ankur aggarwal wrote:
>
> > google question : find triangle in a graph Given an undirected graph,
> > design a O(V+E) algo to detect whether there is a triangle in the
On Sep 6, 5:28 am, ankur aggarwal wrote:
> google question : find triangle in a graph Given an undirected graph,
> design a O(V+E) algo to detect whether there is a triangle in the graph ot
> not.
Just do a depth first search, numbering each node with it's depth as
you find it. If you are sear
@dufus
i read this ques from somewhere .
dont know wat the examiner is looking for...
i think it mite work,,
On Tue, Sep 8, 2009 at 8:38 PM, manish bhatia wrote:
> how about finding all the connected-components and checking which all have
> 3 edges?
>
> --
> *From:*
how about finding all the connected-components and checking which all have 3
edges?
From: ankur aggarwal
To: "i...@mca_2007" ;
lets-talk-g...@googlegroups.com; algogeeks@googlegroups.com
Sent: Sunday, 6 September, 2009 2:58:40 PM
Subject: [algogeeks] find tri
@Nagendra: I think thats exactly what needs to be done.
Triangle is a 3-clique.
Not sure if the interviewer had the same definition in mind.
@Ankur: Please comment.
_dufus
On Sep 7, 8:25 pm, Nagendra Kumar wrote:
> is it not finding a cycle in a graph of length 3.
>
> On Sun, Sep 6, 2009 at
is it not finding a cycle in a graph of length 3.
On Sun, Sep 6, 2009 at 9:02 PM, Dufus wrote:
>
> The following approach might work.
> Let K be the maximum degree of a vertex in the graph
> Enumerate each of the n vertex as 1...n
> Enumerate undirected edge between vertex i and j (i.e. i--j
*"
*
>
> *
> @kunzmilan *
>
* *
> *" What do you mean by polynomial of the 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@g
The following approach might work.
Let K be the maximum degree of a vertex in the graph
Enumerate each of the n vertex as 1...n
Enumerate undirected edge between vertex i and j (i.e. i--j) as
(i,j)
Sort all the |E| edges in O(|V| + |E|) time // radix sort.
Now (i1,i2,i3) form a triangle iff
On Sun, Sep 6, 2009 at 5:47 PM, kunzmilan wrote:
> This problem can be solved by finding polynomial of the graph.
> kunzmilan
>
@kunzmilan : What do you mean by polynomial of the graph ? Is it the cube of
the adjacency matrix?
--~--~-~--~~~---~--~~
You received t
On 6 zář, 11:28, ankur aggarwal wrote:
> google question : find triangle in a graph Given an undirected graph,
> design a O(V+E) algo to detect whether there is a triangle in the graph ot
> not.
This problem can be solved by finding polynomial of the graph.
kunzmilan
--~--~-~--~~--
14 matches
Mail list logo
