weighted tree generation

From: Diego (diego_at_spam.com)
Date: 10/29/04 

Date: Fri, 29 Oct 2004 11:11:39 +0100

Hello,

For a given undirected graph G(V,E) I would like to generate all
possible rooted trees. How many will there be? If there are a lot, at
least I would like to generate a set of different ones or make a single
change to a given tree.

Secondly, is there any standard method to assign weights to an
undirected graph such that for a given root, the all shortest paths
algorithm (e.g.dijkstra) will yield a given tree? (I guess that you
could assign low values to the links that are elements of the tree and
high values for all others, but can it be proven that it will always
yield the given tree?)

And finally, given a weighted graph can I find how much I have to change
  a weight to yield a different shortest path tree for a given root?

Thank you for any answers, comments, references, or just for reading this.

Cheers,
Diego

===
diego at aulignac dot com
www.aulignac.com

Relevant Pages

  • help on graph algorithms - constructing a tree with a mixed criterion
    ... undirected graph. ... to construct a tree T which minimizes the cost with the format ... minimum spanning tree (MST) in graph G, ... As constructing MST and SPT both are in complexity P, ...
    (sci.math)
  • help on constructing a tree with a mixed criterion
    ... undirected graph. ... to construct a tree T which minimizes the cost with the format ... minimum spanning tree (MST) in graph G, ... As constructing MST and SPT both are in complexity P, ...
    (comp.theory)
  • weighted tree generation
    ... For a given undirected graph GI would like to generate all possible ... rooted trees. ... dijkstra) will yield a given tree? ... but can it be proven that it will always yield the given tree?) ...
    (sci.math.research)
  • Re: Another set with cardinality |Z|
    ... In comp.theory Kent Paul Dolan wrote: ... undirected graph with one fewer edges ... What a complicated definition. ... a tree is a strongly connected acyclic graph. ...
    (comp.theory)
  • Re: Another set with cardinality |Z|
    ... In comp.theory Kent Paul Dolan wrote: ... undirected graph with one fewer edges ... What a complicated definition. ... a tree is a strongly connected acyclic graph. ...
    (sci.math)
Loading