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.
16398793
Nowhere-Zero 3-Flows in Squares of Graphs
It was conjectured by Tutte that every 4-edge-connected graph admits a nowherezero 3-flow. In this paper, we give a complete characterization of graphs whose squares admit nowhere-zero 3-flows and thus confirm Tutte’s 3-flow conjecture for the family of squares of graphs.
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.
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.
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.
1748998
Minimum Register Instruction Scheduling: A New Approach for Dynamic Instruction Issue Processors
Modern superscalar architectures with dynamic scheduling and register renaming capabilities have introduced subtle but important changes into the tradeoffs between compile-time register allocation and instruction scheduling. In particular, it is perhaps not wise to increase the degree of parallelism of the static instruction schedule at the expense of excessive register pressure which may result in additional spill code. To the contrary, it may even be beneficial to reduce the register pressure at the expense of constraining the degree of parallelism of the static instruction schedule. This leads to the following interesting problem: given a data dependence graph (DDG) G, can we derive a schedule S for G that uses the least number of registers ? 
 
In this paper, we present a heuristic approach to compute the near-optimal number of registers required for a DDG G (under all possible legal schedules). We propose an extended list-scheduling algorithm which uses the above number of required registers as a guide to derive a schedule for G that uses as few registers as possible. Based on such an algorithm, an integrated approach for register allocation and instruction scheduling for modern superscalar architectures can be developed.
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.
12091703
Indexing and retrieval of 3D models aided by active learning
We demonstrate a system for indexing and retrieval of 3D models aided by active learning. We propose a new set of region-based features for 3D models. Each model is treated as a solid volume with a uniform density. Features such as the volume-surface ratio, the moment invariants and the Fourier transform coefficients are efficiently calculated from the mesh model directly. Comparable retrieval performance is achieved with other features such as the cord histogram, the 3D shape spectrum, etc. To further improve the performance, we incorporate hidden annotation into our system. We propose to use active learning to improve the annotation efficiency. We show that with active learning, the system can perform better than random annotation, and the retrieval result improves rapidly with the number of annotated samples. Moreover, relevance feedback is included in the system and combined with active learning, which provides better user-adoptive retrieval results.
10867502
Robust Visual Tracking via Pixel Classification and Integration
We propose a novel framework for tracking non-rigid objects via pixel classification and integration (PCI). Given a new input frame, the tracker first performs object classification on each pixel and then finds the region that has the highest integral of scores. There are several key advantages of the proposed approach: it is computationally very efficient; it finds a global, instead of local (e.g., mean-shift), optimal solution within a search range; and it is inherently robust to different object scales with minimum extra computation. Within this framework, a mixture of long-term and short-term appearance model is further introduced to perform PCI. As a result, the tracker is able to adapt to both slow and rapid appearance changes without drifting. Challenging video sequences are presented to illustrate how the proposed tracker handles large motion, dramatic shape changes, scale variations, illumination variations and partial occlusions
28540558
A Serving Agent for Integrating Soft Computing and Software Agents
This paper discusses the design and implementation of a serving agent for integrating soft computing and software agents.