Re: tree/cotree extraction

One algorithm that may be useful to get a more "bushy" tree
once you have generated a tree is to select a better
alternative root. It works by starting from all leaves
and successively peel away until you have no more than
2 nodes left, choose one of these as the new (better) root.

As for finding the "centermost" node, perhaps you can start by
finding graph k-centers (e.g., k = 10), and use a similar approach as
above and peel away from these centers till you have
one or two nodes left, and choose one as the root.

Regards,

Yifan Hu
Wolfram Research Inc

David Hysom wrote:

>All,
>
>A colleague of mine inquired about algorithms for extracting
>trees and cotrees from a graph.  After some clarification,
>his conditions and requirements appear to be:
>
>1. the graph results from a finite element dicredtization of a 3D pde;
>   the graph is irregular---some nodes have more edges connected to
>   them than others;
>
>2. he's interested in practice, not theory;
>
>3. the tree should have "branches that are about the same size,"
>   by which I believe he means for any node in the tree, the
>   subtree rooted at the node's children should contain approximately
>   the same number of nodes (i.e., balanced tree);
>
>4. he's looking for a sequential algorithm, but will eventually
>   be interested in a parallel algorithm; at present he's working
>   with 0.5 billion nodes;
>
>5. there is no restriction on choosing the root node;
>
>6. I'm guessing the tree should be as bushy as possible
>   so as to minimize the distance from the root to leaf nodes.
>
>I immediately thought of breadth first search, but don't know
>about dealing with requirements (3) and (6).  I suspect one would want
>to start by finding a "centermost" node and using that as the root.
>
>Any thoughts or references on these issues would be greatly appreciated.
>
>thanks,
>David Hysom
>Center for Advanced Scientific Computing
>Lawrence Livermore Nat. Lab.
>
>
>_______________________________________________
>Csc mailing list
>Csc-lVPF2Jp+hdv2fBVCVOL8/[email protected]
>http://list.odu.edu/listinfo/csc
>
>  
>