Let g_i(n,d,l) denote the number of i-connected labeled cubic graphs of order 2n having exactly d double edges, l loops and no triple edge. For i = 0, 1, and 2 recurrence relations are found for these numbers by counting in two different ways the result of removing an edge.
Solving the recurrence relations using Maple has brought into focus the effect of certain choices on the time complexity of the computations.
Examination of the numbers themselves has suggested a number of facts and conjectures about them.
A cubic graph is one which is 3-regular. A general graph allows loops and multiple edges. After a brief overview of the methods which lead to the recurrence relations, the talk will focus on the time complexity issues and some of the facts and conjectures.
* This is joint work with G.-B. Chae and E. M. Palmer
Given a graph G, an acyclic set A in G is a subset of V(G) such that the induced graph on A is acyclic. Furthermore, A is a maximal acyclic set if it isn't properly contained in any other acyclic set. There's a simple greedy sequential algorithm for finding a maximal acyclic set in a graph, but the same approach doesn't work in a parallel setting, where the goal is to get all of the computation done in poly-logarithmic time on a polynomial number of processors. We'll present a new parallel algorithm for this problem and mention some applications to parallelizing approximation algorithms for the maximum planar subgraph problem and the weighted minimum feedback vertex set problem, as time permits.
There is currently tremendous interest in exploiting the quantum mechanical behavior of matter to process, encrypt, transfer, and store information in ways impossible, or at least practically impossible, by classical or conventional means. Unfortunately, the lack of a scalable architecture with sufficient quantum coherence has prevented this from happening. Last year, however, exciting experiments have demonstrated that certain superconducting devices called Josephson junctions have all the properties required to be used as building blocks of a large-scale quantum computer. These results have produced an explosion of interest in this architecture and a worldwide race to build a quantum computer out of superconductors.
I will give a series of three lectures on these developments. The talks will be geared toward nonspecialists with some exposure to quantum mechanics and quantum computing. The topics to be covered are as follows:
Part I (9/19). Superconductivity and the Josephson effect. Here I will introduce the basics of Bose-Einstein condensation, superconductivity, and the Josephson effect.
Part II (9/26). Superconducting qubits. Here I will explain how to make a qubit, the most basic element of a quantum computer, out of a Josephson junction.
Part III (10/3). Superconducting qubit storage and entanglement. In the final lecture I will describe an architecture we have proposed to couple qubits together to make a viable quantum computer. The architecture makes use of high-frequency mechanical resonators as "bus" qubits to store and transfer the quantum state or wave function of a Josephson junction, and to carry out quantum logic operations.
In both industry and academic research, data mining has become a very "hot" area. In this talk, several leading algorithms in data mining will be examined in detail. For each algorithm, I will start with assumptions, then present a brief algorithm description, discuss its strengths and weaknesses, and finally point out some current research directions.
I will introduce triangulations of a point set, f-vectors, and the size of a triangulation. Some known bounds on the size of a triangulation will be presented. I will also discuss some complexity issues involving the minimal length triangulation (MLT), and an algorithm for finding the MLT for a convex polygon will be given.
A construction and a conjecture about the chromatic number of dense triangle free graphs will be presented. The construction is based on the paper P. Erdos and M. Simomovits, "On a valence problem in extremal graph theory", Discrete Math. 5 (1973).
Mass spectrometry is one of the most popular analytical techniques for identification of individual proteins in a protein mixture, one of the basic problems in modern biology. It identifies a protein through its unique mass spectral pattern. While the problem is theoretically solvable, it remains a challenging problem computationally. One of the key challenges comes from the difficulty in distinguishing the N and C- terminus ions, mostly Y and B ions respectively, in mass spectra. The graph algorithm for solving the problem of separating Y from B ions in a set of mass spectra will be presented. We represent mass spectral data as a graph, considering each spectral peak as a node and relationship between two spectral peaks as a type-1 edge if suspected to be of the same ion type or as a type-2 edge if suspected to be of different types of ions. The problem of separating Y from B ions is formulated and solved as a graph partition problem. The objective of the partition problem is to partition the vertices into three groups so to maximize the number of type-1 edges within y and b ion groups while minimizing the number of type-2 edges within each subgraph. DP approach has been used for the solution.
To fully understand the biological roles of proteins requires knowledge of their structure and function. The gap between structure and sequence determination is getting bigger since the inception of genome sequencing projects. Protein structure prediction is, therefore, going to be vital to bridge the gap. We have developed a threading program to solve the sequence-structure alignment problem. It has several key features. (1) We have developed an efficient way to utilize the evolutionary information for evaluating the threading potentials including singleton and pairwise energies. (2) We have developed a two-stage threading strategy: (a) threading using dynamic programming (DP) without considering pairwise energy and (b) fold recognition considering all energy terms, including the pairwise energy calculated from the DP threading alignments. (3) We have developed a combined z-score scheme for fold recognition, which takes into consideration of z-scores of each energy terms. (4) Based on the z-scores, we have developed a confidence index, which measures the reliability of a prediction and a possible structure-function relationship based on a statistical analysis on a large data set consisting of threadings of 600 query proteins against the entire FSSP templates. Tests on several benchmark sets indicate that the evolutionary information and other new features of PROSPECT greatly improve the alignment accuracy. We also demonstrate that the performance of PROSPECT on fold recognition is significantly better than any other methods available at all levels of similarity. Improvement on the sensitivity of the fold recognition, especially at the superfamily and fold levels, makes PROSPECT a reliable and fully-automated protein structure and function prediction program for genome-scale applications.
The Hidden Subgroup Problem can be defined as follows:
given a function from some finitely generated group G to some set X that is constant on the cosets of an unknown subgroup K, find K.
It turns out that most problems for which "fast" quantum algorithms exist can be described as special cases of this problem. Therefore, an understanding of it (along with an understanding of the Quantum Fourier Transform, which yields a "fast" solution) provides a nice framework for beginning the study of Quantum Algorithms. This talk will begin with a review of some necessary Group Theory required to understand the problem. A discussion of several problems that are special cases of the Hidden Subgroup Problem will follow.
|
| CATS |