@proceedings {38502,
title = {A SIMD solution to the sequence comparison problem on the MGAP},
year = {1994},
month = {1994},
publisher = {IEEE},
type = {10.1109/ASAP.1994.331791},
abstract = {Molecular biologists frequently compare an unknown biosequence with a set of other known biosequences to find the sequence which is maximally similar, with the hope that what is true of one sequence, either physically or functionally, could be true of its analogue. Even though efficient dynamic programming algorithms exist for the problem, when the size of the database is large, the time required is quite long, even for moderate length sequences. In this paper, we present an efficient pipelined SIMD solution to the sequence alignment problem on the Micro-Grain Array Processor (MGAP), a fine-grained massively parallel array of processors with nearest-neighbor connections. The algorithm compares K sequences of length O(M) with the actual sequence of length N, in O(M+N+K) time with O(MN) processors, which is AT-optimal. The implementation on the MGAP computes at the rate of about 0.1 million comparisons per second for sequences of length 128},
keywords = {AT-optimal algorithm, Biological information theory, biology computing, biosequence comparison problem, computational complexity, Computer science, Costs, database size, Databases, DNA computing, dynamic programming, dynamic programming algorithms, fine-grained massively parallel processor array, Genetics, Heuristic algorithms, maximally similar sequence, MGAP parallel computer, Micro-Grain Array Processor, Military computing, molecular biology, molecular biophysics, Nearest neighbor searches, nearest-neighbor connections, Parallel algorithms, pipeline processing, pipelined SIMD solution, sequence alignment problem, sequences},
isbn = {0-8186-6517-3},
author = {Borah, M. and Bajwa, R. S. and Sridhar Hannenhalli and Irwin, M. J.}
}
@proceedings {38208,
title = {A distributed algorithm for ear decomposition},
year = {1993},
month = {1993},
publisher = {IEEE},
type = {10.1109/ICCI.1993.315382},
abstract = {A distributed algorithm for finding an ear decomposition of an asynchronous communication network with n nodes and m links is presented. At the completion of the algorithm either the ears are correctly labeled or the nodes are informed that there exists no ear decomposition. First we present a novel algorithm to check the existence of an ear decomposition which uses O(m) messages. We also present two other algorithms, one which is time-optimal and the other which is message-optimal to determine the actual ears and their corresponding numbers after determining the existence of an ear decomposition},
keywords = {Asynchronous communication, asynchronous communication network, Automata, Communication networks, computational complexity, Computer networks, Computer science, decomposition graph, distributed algorithm, distributed algorithms, Distributed computing, Ear, ear decomposition, graph theory, message-optimal, network decomposition, sorting, Testing, time-optimal},
isbn = {0-8186-4212-2},
author = {Sridhar Hannenhalli and Perumalla, K. and Chandrasekharan, N. and Sridhar, R.}
}
@proceedings {38225,
title = {Efficient algorithms for computing matching and chromatic polynomials on series-parallel graphs},
year = {1992},
month = {1992},
publisher = {IEEE},
type = {10.1109/ICCI.1992.227709},
abstract = {The authors present efficient algorithms for computing the matching polynomial and chromatic polynomial of a series-parallel graph in O(n3) and O(n2) time respectively. Their algorithm for computing the matching polynomial generalizes an existing result from Lovasz, Plummer (1986) and the chromatic polynomial algorithm improves the result given by Hunt, Ravi, Stearn (1988) from O(n4) time},
keywords = {chromatic polynomials, computational complexity, Computer science, graph colouring, graph theory, matching polynomial, Polynomials, series-parallel graphs, Terminology, Tree data structures, Tree graphs},
isbn = {0-8186-2812-X},
author = {Chandrasekharan, N. and Sridhar Hannenhalli}
}