Find Similar Vertices in a graph

Hi
I need a algorithm to find all similar vertices (closed interval) in a
graph. A naive algorithm would be to scan all vertices and match it
with every vertex in the graph. This works well but complexity is
O(n^2)[two for loops]. I wish to reduce it to less O(m + n), where m =
no. of edges in graph, n =no. of vertices. Its possible, I read it in a
paper, but dont have the algorithm.
Can someone help me
Thanks in advance

.

Relevant Pages

  • Re: Standard graph API?
    ... isomorphism graph library. ... It's pretty uniformly agreed that there is no standard graph ... the algorithm can't be specialized for the graph at ... My thought is to use some sort of templating system. ...
    (comp.lang.python)
  • Difference between two systems of DAGs
    ... I am looking for a graph algorithm, ... carry no label or other information except direction. ... edit operations are to change the label of a vertex or the ...
    (comp.theory)
  • Re: Vertex Cover implementation
    ... i code this simple greedy algorithm for the vertex cover: ... As you are constructing your graph you can update the vertex ... each edge appears on two adjacency lists. ... reason to use a priority queue for your algorithm. ...
    (comp.theory)
  • Re: combinatorial optimization problem (six-pick wager grouping)
    ... versed in graph theoretic approaches could comment on my ideas below - ... I'n not a graph theorist, nor a graph algorithm buff, so I can't really ... attempt to merge it with each bet already in the pool. ... million edges when I ignored wager size. ...
    (comp.programming)
  • Re: Pathfinding in community
    ... > Each member is able to add his own contacts at the community. ... Dijkstra's algorithm is simply a refined breadth first search. ... In your case all the edges on the graph have the same weight, ... I would suggest loading this data into an array of arrays. ...
    (comp.lang.php)