29304679
Super line-connectivity of consecutive-d digraphs
Abstract The concept of a consecutive- d digraph was proposed by Du, Hsu and Hwang as a generalization of many digraphs, such as de Bruijn digraphs, Kautz digraphs, and Imase-Itoh digraphs, which contain many hamiltonian digraphs with near-minimum diameter and near-maximum connectivity. In this paper, we show sufficient conditions for modified consecutive- d digraphs to have super line-connectivity.
39315822
A Special Case for Subset Interconnection Designs
Abstract Given a set X and subsets X1, …, Xm, we consider the problem of finding a graph G with vertex set X and the minimum number of edges such that for i = 1,…,m, the subgraph G, induced by Xi is connected. We show that in the special case that every point in X appears in at most three Xi's, the problem is still MAX SNP-complete; however, there exists a polynomial-time approximation within a factor of 5 3 from optimal. As an intermediate result, we also show that the vertex cover problem in cubic graphs is MAX SNP-completc.
11797984
A greedy approximation for minimum connected dominating sets
Given a graph, a connected dominating set is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A minimum connected dominating set is such a vertex subset with minimum cardinality. In this paper, we present a new one-step greedy approximation with performance ratio ln δ + 2 where δ is the maximum degree in the input graph. The interesting aspect is that the greedy potential function of this algorithm is not supmodular while all previously known one-step greedy algorithms with similar performance have supmodular potential functions.
205131274
Performance evaluation of some noise reduction methods
Abstract In this paper, a quantitative evaluation of some noise reduction methods is presented. It first classifies the existing local noise reduction techniques by the use of neighbors and statistics and proposes some new filtering techniques. Subsequently, five performance evaluation criteria including processing time, mean distortion, mean busyness, stability, and correct processing ratio are discussed. By using these performance evaluation criteria, an experiment that involves four factors (test image, noise, mask size, and iteration) was designed to evaluate the performance of the local noise reduction methods. The results indicate that some new local noise reduction techniques have performance better than that of the standard existing techniques under certain criteria.
776913
A dynamic method for dominant point detection
Detecting dominant points is an important step for shape representation. Most of dominant point detection methods attend to preset or find the region of support of each point. In this paper, we demonstrate an improved method for determining the region of support in the dominant point detection. Instead of setting the regions of support for points independently, the region of support dynamically depending on the previous region of support. The experimental results show that the proposed method is effective in detecting dominant points.
8699532
A maximal figure-of-merit learning approach to text categorization
A novel maximal figure-of-merit (MFoM) learning approach to text categorization is proposed. Different from the conventional techniques, the proposed MFoM method attempts to integrate any performance metric of interest (e.g. accuracy, recall, precision, or F1 measure) into the design of any classifier. The corresponding classifier parameters are learned by optimizing an overall objective function of interest. To solve this highly nonlinear optimization problem, we use a generalized probabilistic descent algorithm. The MFoM learning framework is evaluated on the Reuters-21578 task with LSI-based feature extraction and a binary tree classifier. Experimental results indicate that the MFoM classifier gives improved F1 and enhanced robustness over the conventional one. It also outperforms the popular SVM method in micro-averaging F1. Other extensions to design discriminative multiple-category MFoM classifiers for application scenarios with new performance metrics could be envisioned too.
6410764
Dominant point detection using adaptive bending value
Abstract An efficient method for dominant point detection is proposed in this paper. The region of support for each point on curve is determined using bending value. The points with local maximum smoothing bending value can be located as the dominant points on the curve. The proposed algorithm needs no input parameter. The experimental results show that the new method is efficient and effective in detecting dominant points.
35736521
Collision Attack and Pseudorandomness of Reduced-Round Camellia