wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Spanner for a bipartite graph
        
(Message started by: gohan on Feb 8^th, 2007, 5:44am)

Title: Spanner for a bipartite graph
Post by gohan on Feb 8^th, 2007, 5:44am

Hi all,
can somebody suggest me a spanner for a bipartite graph?

Title: Re: PLs Help me out
Post by CowsRUs on Feb 8^th, 2007, 3:00pm

Better titles?
dont write plz help me out ;)

Title: Re: Spanner for a bipartite graph
Post by Icarus on Feb 8^th, 2007, 4:56pm

on 02/08/07 at 15:00:08, CowsRUs wrote:

Better titles?
dont write plz help me out ;)

It's a losing battle, but we fight on anyway!

on 02/08/07 at 05:44:42, gohan wrote:

Hi all,
can somebody suggest me a spanner for a bipartite graph?

Not exactly sure what you mean by a "spanner". A spanning tree, perhaps? But then, I can't just specify one - it would depend on the graph.

Are you after an algorithm for finding a spanning tree, perhaps?

Title: Re: Spanner for a bipartite graph
Post by CowsRUs on Feb 8^th, 2007, 4:58pm

nice, admin pwrs... I'd think u'd delete my three new threads... in easy ;D ;D ;D

Title: Re: Spanner for a bipartite graph
Post by THUDandBLUNDER on Feb 13^th, 2007, 11:01am

on 02/08/07 at 16:56:36, Icarus wrote:

Not exactly sure what you mean by a "spanner". A spanning tree, perhaps? But then, I can't just specify one - it would depend on the graph.

Possibly:
A tree t spanner of a graph G is a spanning tree of G in which the distance between every pair of vertices is at most t times their distance in G.

But if he is just looking for a tree spanner (http://dictionary.reference.com/search?q=spanner&x=0&y=0) then maybe a monkey wrench would do. ;)