Recent Papers, Slides and Codes Relevant to This Project
High Performance Computational Tools for Motif Discovery,
N. E. Baldwin, R. L. Collins, M. A. Langston, M. R. Leuze, C. T. Symons and
B. H. Voy,
Proceedings, IEEE International Workshop on High Performance Computational Biology,
April, 2004.

Most differences in organism complexity are due to elements of gene regulation
that reside in non protein coding portions of genes.
Powerful new motif finding algorithms and high performance implementations are
developed in order to identify and study these regulatory elements.
Heavy use is made of graph algorithms and fully dynamic parallel load balancing.
Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments,
F. N. AbuKhzam, R. L. Collins, M. R. Fellows, M. A. Langston, W. H. Suters,
and C. T. Symons,
Proceedings, ACMSIAM Workshop on Algorithm Engineering and Experiments,
January, 2004.

A variety of efficient kernelization strategies are developed, implemented and
tested for the classic vertex cover problem. A new technique, termed crown
reduction, is introduced and analyzed. Applications to computational
biology are discussed.

Graph algorithms are employed to analyze differential gene expression data.
Clique and dominating set are used to train algorithms for tissue classification
using patient populations with known disease profiles. It is shown that these
algorithms can then be used in tandem to classify and predict the likelihood of
disease in patient populations whose profiles are not known in advance.

A novel combination of emergent algorithmic methods, powerful computational
platforms and supporting infrastructure is described. Efficient algorithms
are devised and implemented. Optimal solutions to very large instances of
the vertex cover problem are computed. The importance of maintaining a
balanced decomposition of the search space is shown to be critical to achieving
scalability.

A presentation summarizes a talk given to ORNL's Computational Biology Institute,
October, 2003.
Progress on Perfect Graphs,
M. Chudnovsky, N. Robertson, P. D. Seymour and R. Thomas,
Mathematical Programming Series B
97 (2003), 405422.

The main aspects of perfect graphs and their relevance are surveyed.
The authors outline their recent proof of the Strong Perfect Graph
Conjecture originally made by Berge in 1961.
Clustal XP,
F. N. AbuKhzam, J. J. Cheetham, F. Dehne, M. A. Langston, S. Pitre, A. RauChaplin, P. Shanbhag and P. J. Taillon, 2003.

This portal provides powerful new software tools for the computational
biology community. It features a highperformance parallel version of
the popular Clustal W package, plus cuttingedge vertex cover codes for
use in phylogenetic applications.

A presentation summarizes a talk given to UT's Innovative Computing Laboratory.

The disk dimension and face cover problems are studied. Both are aimed at
finding small sets of faces in planar graphs. A number of results are derived,
including a lineartime 3approximation algorithm for the pathwidth problem on
graphs of fixed disk dimension, and a sizable improvement over the best
previouslypublished face cover algorithm.
Graph Coloring and the Immersion Order,
F. N. AbuKhzam and M. A. Langston,
Proceedings, International Conference on Computing and Combinatorics, July, 2003.

The relationship between graph coloring and the immersion order is considered.
It is conjectured that, if G requires at least t
colors, then G must have immersed within it the complete graph on
t vertices. It is proved that minimal counterexamples must, if any
exist, be both 4vertexconnected and tedgeconnected.
Slides
are also available for this paper.
Grid Computing,
F. N. AbuKhzam and M. A. Langston.

Presentations summarize a tutorial series delivered at the HICSS36
International Conference, January, 2003.

Decompositions based on branchwidth provide a natural framework for
implementing dynamic programming algorithms.
A heuristic branchdecomposition method is described based on the
eigenvector technique for finding graph separators.
This tool is used to obtain highquality tours for the traveling salesman
problem by merging collections of tours produced by standard heuristics.

G is perfect if for every induced subgraph H, the chromatic
number of H equals the size of the largest complete subgraph of H.
G is Berge if no induced subgraph of G is an odd cycle of
length at least 5 or the complement of such a cycle.
The paper proves the strong perfect graph conjecture, showing that a
a graph is perfect if and only if it is Berge.
Slides
are also available for this paper.
2002.

Presentations summarize a series of lectures delivered at the NSFCBMS Regional
Conference, 2002.

A shredder in an undirected graph is a set of vertices whose removal results in
at least three components. A 3shredder is a shredder of size three. We
present an algorithm that, given a 3connected graph, finds its threeshredders
in time proportional to the number of vertices and edges, when implemented on a
random access machine.
2002.
Distributed Dimension Reduction Algorithms for Widely Dispersed Data,
F. N. AbuKhzam, N. Samatova, G. Ostrouchov, M. A. Langston and Al Geist,
Proceedings, International Conference on Parallel and Distributed Computing and Systems, 2002.

Information retrieval, clustering and visualization can often be improved by
reducing the dimensionality of high dimensional data. An effective distributed
dimension reduction algorithm is developed based on the serial (nondistributed)
FastMap heuristic of Faloutsos and Lin. A series of experiments suggest that
the new method is shown to be fast, accurate and reliable.
On SpecialPurpose Hardware Clusters for HighPerformance Computational
Grids,
J. M. Lehrter, F. N. AbuKhzam, D. W. Bouldin, M. A. Langston and G. D.
Peterson,
Proceedings, International Conference on Parallel and Distributed Computing and Systems, 2002.

An experimental specialpurpose cluster of machines is designed and placed into
service on a prototypical grid.
The cluster is populated with CAD workstations, PCs and reconfigurable devices,
and then used to develop accelerated implementations for amenable applications.
Access mechanisms are devised so that users may request either software
or accelerated hardware solutions.
Automatic Mapping of Multiple Applications to Multiple Adaptive Computing
Systems,
S. Ong, N. Kerkiz, B. Srijanto, C. Tan, M. A. Langston, D. F. Newport and
D. W. Bouldin,
Proceedings, IEEE Symposium on FieldProgrammable Custom Computing Machines, 2001.

Traditional methods for mapping applications onto adaptive computing systems
can take months to develop and debug. To automate and speed this process, a
software design environment has been developed at the University of Tennessee.
This environment permits highlevel design entry and eliminates the need for
handling lowlevel details of the target hardware architecture.
On Computing Graph Minor Obstruction Sets,
K. Cattell, M. J. Dinneen, R. G. Downey, M. R. Fellows and M. A. Langston,
Theoretical Computer Science 233 (2000), 107127.

The Graph Minor Theorem establishes that many natural graph properties can be
characterized by a finite set of forbidden substructures. Several general
theorems regarding the computation these substructures are proved. New
algorithmic techniques are introduced and extended to other partial orders,
including immersion and topological containment.
Fast Algorithms for K4 Immersion Testing,
H. D. Booth, R. Govindan, M. A. Langston and S. Ramachandramurthi,
Journal of Algorithms 30 (1999), 344378.

Many useful classes of graphs can in principle be recognized with finite
batteries of obstruction tests. One of the most fundamental tests is to
determine whether an arbitrary input graph has immersed within it the
complete graph of order four. The first fast, practical algorithms
(both serial and parallel) are presented to accomplish this task.