HYPERTREE, GR
Hypertree (also called gr) - an efficient program for solving the Graph Realization Problem.
As a byproduct of writing the program GPPH (also known as PPH), we created
a stand alone program for solving the graph realization problem.
Let E_r a set of r distinct integers. A ``path set" is an unordered
subset P of E. A path set is ``realized" in a undirected, edge-labeled
tree T consisting of r edges, if each edge of T is labeled by a
distinct integer from E_r, and there is a contiguous path in T
whose labels consist of the integers in P. Note that since P is
unordered, it's presentation does not specify or constrain the
order that those edges appear in T. In quite different terms, from
the 1930's to the 1960's Whitney and Tutte and others studied and
solved the following problems:
The Graph Realization Problem: Given E_r and a family Pi = {P_1,
P_2, ... , P_k} of path sets defined on E_r, find a tree T in which
each path set is realized, or determine that no such tree exists.
The program implements the graph realization method in the paper:
"An algorithm for constructing edge-trees from hypergraphs",
Fanica Gavril and Robert Tamari, Networks, vol. 13, 1983
That paper is written in the language of hypergraphs, and hence the program
is called Hypertree, but the problem solved is exactly the graph realization problem.
This package was written by Ren-Hua Chung at U.C. Davis Computer Science under the
direction of Dan Gusfield.
To see how the graph realization problem is used to solve the perfect
phylogeny haplotyping problem, see:
"Haplotyping as Perfect Phylogeny: Conceptual Framework and Efficient Solutions"
in
recent papers
Copyright (C) 2002 R.H. Chung and D. Gusfield
We give no warranties, and no rights for commercial use.
Executable versions of program hypertree (gr) are available for the following platforms: