16072775
PC trees and circular-ones arrangements
A 0-1 matrix has the consecutive-ones property if its columns can be ordered so that the ones in every row are consecutive. It has the circular-ones property if its columns can be ordered so that, in every row, either the ones or the zeros are consecutive. PQ trees are used for representing all consecutive-ones orderings of the columns of a matrix that have the consecutive-ones property. We give an analogous structure, called a PC tree, for representing all circular-ones orderings of the columns of a matrix that has the circular-ones property. No such representation has been given previously. In contrast to PQ trees, PC trees are unrooted. We obtain a much simpler algorithm for computing PQ trees that those that were previously available, by adding a zero column, x, to a matrix, computing the PC tree, and then picking the PC tree up by x to root it.
6232755
Algorithms for minimum covering by cliques and maximum clique in claw-free perfect graphs
An algorithm is given for determining a minimum cardinality clique cover ongraphs that do not contain claws, odd holes or odd anti-holes. These graphs are also shown to be perfect so that we obtain a new proof of the strong perfect graph theorem for claw-free graphs. A by-product of our analysis is an algorithm for determining a maximum cardinality clique on claw-free perfect graphs.
17795095
A Simple Test for the Consecutive Ones Property
A (0,1)-matrix satisfies the consecutive ones property if there exists a column permutation such that the one's in each row of the resulting matrix are consecutive. Booth and Lueker [1976] designed a linear time testing algorithm for this property based on a data structure called “PQ-trees”. This procedure is very complicated and the linear time amortized analysis is also rather involved. We develop an off-line testing algorithm for the consecutive ones property without using PQ-trees. Our approach is based on a decomposition technique which separates the rows into “prime” subsets which admit unique column orderings that realize the consecutive ones property. The success of this approach is based on finding a good “row ordering” to be tested iteratively.
208691
Coloring planar perfect graphs by decomposition
This paper describes a decomposition scheme for coloring perfect graphs. Based on this scheme, one need only concentrate on coloring highly connected (at least 3-connected) perfect graphs. This idea is illustrated on planar perfect graphs, which yields a straightforward coloring algorithm. We suspect that, under appropriate definition, highly connected perfect graphs might possess certain regular properties that are amenable to coloring algorithms.
2164726
A New Planarity Test
Abstract Given an undirected graph, the planarity testing problem is to determine whether the graph can be drawn in a plane without any crossing edges. Linear time planarity testing algorithms have previously been designed by Hopcroft and Tarjan, and by Booth and Lueker. However, their approaches are quite involved. Several other approaches have also been developed for simplifying the planarity test. In this paper, we developed a very simple linear time testing algorithm based only on a depth-first search tree. When the given graph is not planar, our algorithm immediately produces explicit Kuratowski's subgraphs. A new data structure, PC -trees, is introduced, which can be viewed as abstract subembeddings of actual planar embeddings. A graph-reduction technique is adopted so that the embeddings for the planar biconnected components constructed at each iteration never have to be changed. The recognition and embedding are actually done simultaneously in our algorithm (Booth and Lueker, 1976). The implementation of our algorithm is quite straightforward.
2987495
Independent Sets in Circular-Arc Graphs
This paper presents a linear time algorithm for the independent set problem on circular-arc graphs. previous algorithms for this problem have assumed that the input is a set of circular-arcs and solve the problem in O(n) time. However, the fastest known algorithm for constructing the circular-are representation from a set of adjacency lists takes O(n2) time. We show that we can solve the problem in O(n + m) time, when we are given the circular-arc graph as a set of adjacency lists.
14566859
Various criteria in the evaluation of biomedical named entity recognition
BackgroundText mining in the biomedical domain is receiving increasing attention. A key component of this process is named entity recognition (NER). Generally speaking, two annotated corpora, GENIA and GENETAG, are most frequently used for training and testing biomedical named entity recognition (Bio-NER) systems. JNLPBA and BioCreAtIvE are two major Bio-NER tasks using these corpora. Both tasks take different approaches to corpus annotation and use different matching criteria to evaluate system performance. This paper details these differences and describes alternative criteria. We then examine the impact of different criteria and annotation schemes on system performance by retesting systems participated in the above two tasks.ResultsTo analyze the difference between JNLPBA's and BioCreAtIvE's evaluation, we conduct Experiment 1 to evaluate the top four JNLPBA systems using BioCreAtIvE's classification scheme. We then compare them with the top four BioCreAtIvE systems. Among them, three systems participated in both tasks, and each has an F-score lower on JNLPBA than on BioCreAtIvE. In Experiment 2, we apply hypothesis testing and correlation coefficient to find alternatives to BioCreAtIvE's evaluation scheme. It shows that right-match and left-match criteria have no significant difference with BioCreAtIvE. In Experiment 3, we propose a customized relaxed-match criterion that uses right match and merges JNLPBA's five NE classes into two, which achieves an F-score of 81.5%. In Experiment 4, we evaluate a range of five matching criteria from loose to strict on the top JNLPBA system and examine the percentage of false negatives. Our experiment gives the relative change in precision, recall and F-score as matching criteria are relaxed.ConclusionIn many applications, biomedical NEs could have several acceptable tags, which might just differ in their left or right boundaries. However, most corpora annotate only one of them. In our experiment, we found that right match and left match can be appropriate alternatives to JNLPBA and BioCreAtIvE's matching criteria. In addition, our relaxed-match criterion demonstrates that users can define their own relaxed criteria that correspond more realistically to their application requirements.
5724385
An iterative relaxation technique for the NMR backbone assignment problem
NMR spectroscopy is one of the popular experiments to determine protein structures. An important stage of protein structure determination by using NMR is protein backbone resonance assignment (or backbone assignment for short). Due to the messiness and disorder of NMR spectral data, backbone assignment is usually a tedious and time-consuming manual work. This raises a great interest in developing an efficient and automatic method to perform backbone assignment. An iterative algorithm is proposed that is equipped with two operations: grouping and linking. Grouping is responsible for peak picking and part of connectivity determination. Ideally, those peaks with the same H/sup N/ and N chemical shifts can be grouped together; peaks belonging to the same group can be used to determine the order of two consecutive spin systems. However, in real situation, grouping is a difficult task due to false positives and false negatives. We sometimes add hypothetic peaks to tackle false negatives and use linking operation to remove false positives. Linking is responsible for part of connectivity determination and backbone assignment. Given a protein sequence and partial connectivity information, we try to link connected spin systems as much as possible. False positive spin systems may create conflicts in the linking stage. To find a good assignment on a noisy dataset, the backbone assignment problem is modeled as a maximum independent set problem. Although the problem is NP-complete, there are heuristic methods that obtain pretty good results.
9113597
Designing an ontology-based intelligent tutoring agent with instant messaging
The rapid growth of the Internet and instant messaging (IM) offers new opportunities as well as challenges to both educators and students. In this paper, we propose an intelligent tutoring agent (ITA) that uses the ontology, INFOMAP, and question answering techniques through the instant messaging platform for the "operating system " course. The ITA embeds the above techniques in the teaching process and plays the role of a tutoring agent to help a teacher track, record, and understand a student's status. The ITA interface can interpret natural language to facilitate communication between the student and the tutor. Student can query and learn the concept of "operating system" through MSN Messenger, which ITA adopts as the communication protocol. The proposed ITA is accessible by adding the contact ID: iaslita@hotmail.com to the MSN Messenger contacts list.
7586483
Video search reranking via information bottleneck principle
We propose a novel and generic video/image reranking algorithm, IB reranking, which reorders results from text-only searches by discovering the salient visual patterns of relevant and irrelevant shots from the approximate relevance provided by text results. The IB reranking method, based on a rigorous Information Bottleneck (IB) principle, finds the optimal clustering of images that preserves the maximal mutual information between the search relevance and the high-dimensional low-level visual features of the images in the text search results. Evaluating the approach on the TRECVID 2003-2005 data sets shows significant improvement upon the text search baseline, with relative increases in average performance of up to 23%. The method requires no image search examples from the user, but is competitive with other state-of-the-art example-based approaches. The method is also highly generic and performs comparably with sophisticated models which are highly tuned for specific classes of queries, such as named-persons. Our experimental analysis has also confirmed the proposed reranking method works well when there exist sufficient recurrent visual patterns in the search results, as often the case in multi-source news videos.
17603178
A Linear Time Algorithm for Finding a Maximal Planar Subgraph Based on PC-Trees
In Shih & Hsu, a planarity test was introduced utilizing a data structure called PC-trees, generalized from PQ-trees. They illustrated that a PC-tree is more natural in representing planar graphs. Their algorithm starts by constructing a depth-first-search tree and adds all back edges to a vertex one by one. An important feature in the S&H algorithm is that, at each iteration, at most two terminal nodes need to be computed and the unique tree path between these two nodes provides essentially the boundary path of the newly formed biconnected component. 
 
In this paper we modify their PC-tree algorithm and introduce the deferred planarity test (DPT), which has the added benefit of finding a maximal planar subgraph (MPS) in linear time when the given graph is not planar. DPT is an incremental algorithm, which only computes a partial terminal path at each iteration. DPT continually deletes back edges that could create a violation to the formation of those partial terminal paths so that, at the end, the subgraph constructed is guaranteed to be planar. 
 
The key to the efficiency of the S&H and the DPT algorithms lies in their management on the creation and destruction of biconnected components in which the PC-tree plays a major role. Previously, there have been reports that the MPS problem can be solved in linear time. However, there was no concrete data structure realizing them.