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. Abu-Khzam, R. L. Collins, M. R. Fellows, M. A. Langston, W. H. Suters, and C. T. Symons, Proceedings, ACM-SIAM 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.

A Combinatorial Approach to the Analysis of Differential Gene Expression Data: The Use of Graph Algorithms for Disease Prediction and Screening, M. A. Langston, L. Lin, X. Peng, N. E. Baldwin, C. T. Symons and B. Zhang, Proceedings, International Conference for the Critical Assessment of Microarray Data Analysis, November, 2003.

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.

Scalable Parallel Algorithms for Difficult Combinatorial Problems: A Case Study in Optimization, F. N. Abu-Khzam, M. A. Langston and P. Shanbhag, Proceedings, International Conference on Parallel and Distributed Computing and Systems, November, 2003.

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.

High-Performance Computational Tools for Biological Applications, M. A. Langston, 2003.

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), 405-422.

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. Abu-Khzam, J. J. Cheetham, F. Dehne, M. A. Langston, S. Pitre, A. Rau-Chaplin, P. Shanbhag and P. J. Taillon, 2003.

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

Fixed-Parameter Tractability: Foundations, Implementations and Applications, M. A. Langston, 2003.

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

Faces in the Crowd: On the Algorithmic Utility of Disks and Covers, F. N. Abu-Khzam and M. A. Langston, 2003.

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 linear-time 3-approximation algorithm for the pathwidth problem on graphs of fixed disk dimension, and a sizable improvement over the best previously-published face cover algorithm.

Graph Coloring and the Immersion Order, F. N. Abu-Khzam 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 4-vertex-connected and t-edge-connected. Slides are also available for this paper.

Grid Computing, F. N. Abu-Khzam and M. A. Langston.

Presentations summarize a tutorial series delivered at the HICSS-36 International Conference, January, 2003.

Tour Merging via Branch-Decomposition, W. Cook and P. Seymour, INFORMS Journal on Computing 15 (2003), 233-248.

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

The Strong Perfect Graph Theorem, M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas.

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.

On Graph Structure and Decomposition, R. Thomas.

Presentations summarize a series of lectures delivered at the NSF-CBMS Regional Conference, 2002.

Finding 3-Shredders Efficiently, R. Hegde.

A shredder in an undirected graph is a set of vertices whose removal results in at least three components. A 3-shredder is a shredder of size three. We present an algorithm that, given a 3-connected graph, finds its three-shredders 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. Abu-Khzam, 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 (non-distributed) FastMap heuristic of Faloutsos and Lin. A series of experiments suggest that the new method is shown to be fast, accurate and reliable.

On Special-Purpose Hardware Clusters for High-Performance Computational Grids, J. M. Lehrter, F. N. Abu-Khzam, D. W. Bouldin, M. A. Langston and G. D. Peterson, Proceedings, International Conference on Parallel and Distributed Computing and Systems, 2002.

An experimental special-purpose 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 Field-Programmable 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 high-level design entry and eliminates the need for handling low-level 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), 107-127.

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), 344-378.

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.