@proceedings {38555, title = {Uncovering Genomic Reassortments among Influenza Strains by Enumerating Maximal Bicliques}, year = {2008}, month = {2008}, publisher = {IEEE}, type = {10.1109/BIBM.2008.78}, abstract = {The evolutionary histories of viral genomes have received significant recent attention due to their importance in understanding virulence and the corresponding ramifications to public health. We present a novel framework to detect reassortment events in influenza based on the comparison of two distributions of phylogenetic trees, rather than a pair of, possibly unreliable, consensus trees. We show how to detect all high-probability inconsistencies between two distributions of trees by enumerating maximal bicliques within a defined incompatibility graph. In the process, we give the first quadratic delay algorithm for enumerating maximal bicliques within general bipartite graphs. We demonstrate the utility of our approach by applying it to several sets of influenza genomes (both human- and avian-hosted) and successfully identify all known reassortment events and a few novel candidate reassortments. In addition, on simulated datasets, our approach correctly finds implanted reassortments and rarely detects reassortments where none were introduced.}, keywords = {avian hosted influenza genome, Bioinformatics, Capacitive sensors, Delay, diseases, Event detection, general bipartite graphs, genomic reassortments, Genomics, graph theory, high probability inconsistencies, History, human hosted influenza genome, incompatibility graph, Influenza, influenza strain, maximal biclique, maximal biclique enumeration, microorganisms, phylogenetic trees, Phylogeny, Public healthcare, quadratic delay algorithm, reassortment, reassortment event detection, Tree graphs, viral genome evolutionary history, virulence}, isbn = {978-0-7695-3452-7}, author = {Nagarajan, N. and Kingsford, Carl} } @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} }