46565546
Arc-disjoint circuits in digraphs
36530209
Determination of the star valency of a graph
The star valency of a graph G is the minimum, over all star decompositions π, of the maximum number of elements in π incident with a vertex. The maximum average degree of G, denoted by dmax-ave(G), is the maximum average degree of all subgraphs of G. In this paper, we prove that the star valency of G is either ⌈dmax-ave(G)/2⌉ or ⌈dmax-ave(G)/2⌉ + 1, and provide a polynomial time algorithm for determining the star valency of a graph.
13303898
Chords of longest circuits in 3-connected graphs
Thomassen conjectured that every longest circuit of a 3-connected graph has a chord. The conjecture is verified in this paper for projective planar graphs with minimum degree at least 4.
21169395
Small Circuit Double Covers of Cubic Multigraphs
Let G be a two-connected graph. A family F of circuits of G is called a circuit double cover (CDC) if each edge of G is contained in exactly two circuits of F. In this paper, we show that if a simple cubic graph G (G ? K4) of order n has a CDC, then G has a CDC containing at most n/2 circuits. This result establishes the equivalence of the circuit double cover conjecture (due to Szekeres, Seymour) and the small circuit double cover conjecture (due to Bondy) for any cubic graph. Actually, a stronger result is obtained in this paper for all loopless cubic graphs. Another result in this paper establishes an upper bound on the size of any CDC of a cubic graph.
17086856
A note about shortest cycle covers
Let G be a graph with odd edge-connectivity r. It is proved in this paper that if r>3, then G has a 3-cycle (1,2)-cover of total length at most ((r+1)|E(G)|)/r.
11462933
On flows in bidirected graphs
Bouchet conjectured that every bidirected graph which admits a nowhere-zero bidirected flow will admit a nowhere-zero bidirected 6-flow [A. Bouchet, Nowhere-zero integer flows on a bidirected graph, J. Combin. Theory Ser. B 34 (1983) 279-292]. He proved that this conjecture is true with 6 replaced by 216. Zyka proved in his Ph.D dissertation that it is true with 6 replaced by 30. Khelladi proved it is true with 6 replaced with 18 for 4-connected graphs [A. Khelladi, Nowhere-zero integer chains and flows in bidirected graphs, J. Combin. Theory Ser. B 43 (1987) 95-115]. In this paper, we prove that Bouchet's conjecture is true for 6-edge connected bidirected graphs.
6417923
Analysis of Sound Features for Music Timbre Recognition
Recently, communication, digital music creation, and computer storage technology has led to the dynamic increasing of online music repositories in both number and size, where automatic content-based indexing is critical for users to identify possible favorite music pieces. Timbre recognition is one of the important subtasks for such an indexing purpose. Lots of research has been carried out in exploring new sound features to describe the characteristics of a musical sound. The moving picture expert group (MPEG) provides a standard set of multimedia features, including low level acoustical features based on latest research in this area. This paper introduces our newly designed temporal features used for automatic indexing of musical sounds and evaluates them with MPEG7 descriptors, and other popular features.
40464778
A model for compressing probabilities in belief networks
Probabilistic reasoning with belief (Bayesian) networks is based on conditional probability matrices. Thus it suffers from NP-hard implementations. In particular, the amount of probabilistic information necessary for the computations is often overwhelming. So, compressing the conditional probability table is one of the most important issues faced by the probabilistic reasoning community. Santos suggested an approach (called linear potential functions) for compressing the information from a combinatorial amount to roughly linear in the number of random variable assignments. However, much of the information in Bayesian networks, in which there are no linear potential functions, would be fitted by polynomial approximating functions rather than by reluctantly linear functions. For this reason, we construct a polynomial method to compress the conditional probability table in this paper. We evaluated the proposed technique, and our experimental results demonstrate that the approach is efficient and promising.
1085378
Profiling alternatively spliced mRNA isoforms for prostate cancer classification
BackgroundProstate cancer is one of the leading causes of cancer illness and death among men in the United States and world wide. There is an urgent need to discover good biomarkers for early clinical diagnosis and treatment. Previously, we developed an exon-junction microarray-based assay and profiled 1532 mRNA splice isoforms from 364 potential prostate cancer related genes in 38 prostate tissues. Here, we investigate the advantage of using splice isoforms, which couple transcriptional and splicing regulation, for cancer classification.ResultsAs many as 464 splice isoforms from more than 200 genes are differentially regulated in tumors at a false discovery rate (FDR) of 0.05. Remarkably, about 30% of genes have isoforms that are called significant but do not exhibit differential expression at the overall mRNA level. A support vector machine (SVM) classifier trained on 128 signature isoforms can correctly predict 92% of the cases, which outperforms the classifier using overall mRNA abundance by about 5%. It is also observed that the classification performance can be improved using multivariate variable selection methods, which take correlation among variables into account.ConclusionThese results demonstrate that profiling of splice isoforms is able to provide unique and important information which cannot be detected by conventional microarrays.
2813515
Re-factoring Middleware Systems: A Case Study
Aspect oriented programming brings us new design perspectives since it permits the superimpositions of multiple abstraction models on top of one another. It is a very powerful technique in separating and simplifying design concerns. In this paper, we provide detailed descriptions of our aspect oriented re-factoring of ORBacus, an industrial strength CORBA implementation. The re-factored features are the dynamic programming interface, support for portable interceptors, invocations of local objects. Their associated IDL-level re-factorization is addressed by an aspect-aware IDL compiler. In addition, we present the quantification for the changes in terms of both the structural complexity and the runtime performance. The aspect oriented re-factorization proves that AOP is capable of composing non-trivial functionality of middleware in a superimposing manner. The final “woven” system is able to correctly provide both the fundamental functionality and the “aspectized” functionality with negligible overhead and leaner architecture. Furthermore, the “aspectized” feature can be configured in and out during compile-time, which greatly enhances the configurability of the architecture.
6853058
Markov chain correlation based clustering of gene expression data
An efficient Markov chain correlation based clustering method (MCC) has been proposed for clustering gene expression data. The gene expression data is first normalized and Markov chains (MC) are constructed from the dynamics of the gene expressions, in which the behavior of the genes at each step of the experiment can be taken into account. Based on the correlation of one-step Markov chain transition probabilities, an agglomerative method is employed to group the series that have similar behavior at each point. The proposed MCC clustering method has been applied to four gene expression datasets to obtain a number of clusters. The results show that the MCC method outperforms the commonly used K-means method and produces clusters that are more meaningful in terms of the similarity of the grouped genes. Another advantage of the proposed method over the existing clustering methods is that the knowledge of the group number is not required.