Engineering: Reportshttp://hdl.handle.net/10092/6112016-08-26T01:25:03Z2016-08-26T01:25:03ZA smalltalk queueing network simulatorIrwin, Warwickhttp://hdl.handle.net/10092/125902016-08-23T15:01:00Z1989-01-01T00:00:00ZA smalltalk queueing network simulator
Irwin, Warwick
This report gives complete documentation for a working implementation of a discrete, event driven Smalltalk-80 modelling context described in Goldberg and Robson "Smalltalk-80: The Language and its Implementation". It also documents DEMOS-derived enhancements to this simulation system and methods for improved presentation of results. The system is running under Apple's level0 image on a Macintosh plus computer. It uses only standard Smalltalk-80 and will be portable to any other standard Smalltalk system. An extremely brief introduction to Smalltalk, source code and example programs are given as appendices.
1989-01-01T00:00:00ZThe difficulty of constructing a leaf-labelled tree including or avoiding given subtreesNg, Meei PyngSteel, M.Wormald, N.http://hdl.handle.net/10092/125772016-08-15T15:00:58Z1995-01-01T00:00:00ZThe difficulty of constructing a leaf-labelled tree including or avoiding given subtrees
Ng, Meei Pyng; Steel, M.; Wormald, N.
Given a set of trees with leaves labelled from a set L, is there a
tree T with leaves labelled by L such that each of the given trees is
homeomorphic to a subtree of T? This question is known to be NPcomplete
in general, but solvable in polynomial time if all the given
trees have one label in common ( equivalently, if the given trees are
rooted). Here we show that this problem is NP-complete even if there
are two labels x and y such that each given tree contains x or y. On
the other hand, we show that the question of whether a fully resolved
(binary) tree exists which has no subtree homeomorphic to one of
the given ones is NP-complete, even when the given trees are rooted.
This sheds some light on the complexity of determining whether a
probability assignment to trees is coherent.
1995-01-01T00:00:00ZTree representations of non-symmetric group-valued proximitiesSemple, CharlesSteel, M.http://hdl.handle.net/10092/125762016-08-15T15:00:57Z1999-01-01T00:00:00ZTree representations of non-symmetric group-valued proximities
Semple, Charles; Steel, M.
Let X be a finite set and let d be a function from X x X into an
arbitrary group Q. An example of such a function arises by taking a tree T
whose vertices include X, assigning two elements of Q to each edge of T ( one
for each orientation of the edge), and setting d(i,j) equal to the product of the
elements along the directed path from i to j. We characterize conditions when
an arbitrary function d can be represented in this way, and show how such
a representation may be explicitly constructed. We also describe the extent
to which the underlying tree and the edge weightings are unique in such a
representation. These results generalize a recent theorem involving undirected
edge assignments by an Abelian group. The non-Abelian bi-directed case is of
particular relevance to phylogeny reconstruction in molecular biology.
1999-01-01T00:00:00ZExperimental and theoretical analysis of hybridizationLinz, SimoneSt. John, K.Semple, Charleshttp://hdl.handle.net/10092/125752016-08-15T15:00:55Z2006-01-01T00:00:00ZExperimental and theoretical analysis of hybridization
Linz, Simone; St. John, K.; Semple, Charles
We develop new heuristics and
an exact algorithm for calculating the
amount of hybridization between two
rooted binary phylogenetic trees. Calculating
the minimum number of hybridization
events is NP-hard, but essential to
understanding the modeling of reticulation
processes such as hybridization, horizontal
gene transfer, and recombination. We
give new lower bounds for the hybridization
number that are very useful in limiting
search times for exact answers and in
conjunction with existing upper bounds to
"sandwich" the true answer. We analyze
the algorithms experimentally on both biological
and simulated data.
2006-01-01T00:00:00Z