13557005
Vertex Cover: Further Observations and Further Improvements
Recently, there has been increasing interest and progress in lowering the worst-case time complexity for well-known NP-hard problems, particularly for the Vertex Cover problem. In this paper, new properties for the Vertex Cover problem are indicated, and several simple and new techniques are introduced, which lead to an improved algorithm of time O(kn+1.2852k) for the problem. Our algorithm also induces improvement on previous algorithms for the Independent Set problem on graphs of small degree.
31382426
Strong Fault-Tolerance: Parallel Routing in Networks with Faults
A d-regular network G is strongly fault-tolerant if for any copy Gf of G with at most d - 2 faulty nodes, every pair of nonfaulty nodes u and v in Gf admits min{df(u), df (v)} node-disjoint paths in Gf from u to v, where df(u) and df(v) are the degrees of the nodes u and v in Gf. We show that popular network structures, such as hypercube and star networks, are strongly fault-tolerant. We develop efficient algorithms that construct the maximum number of node-disjoint paths of optimal or nearly optimal length in these networks with faulty nodes. Our algorithms are optimal in terms of their running time.
5242879
Interactive rind modeling
In this paper, we describe a technique, with roots in topological graph theory, that we call rind modeling. It provides for the easy creation of surfaces resembling peeled and punctured rinds. We show how the method's two main steps of: 1) creation of a shell or crust like the rind of an orange, and 2) opening holes in the crust by punching or peeling can be encapsulated into a real time semi-automatic interactive algorithm. We include a number of worked examples, some by students in a first modeling course, that demonstrate the ease with which a large variety of intricate rind shapes can be created.
16331940
Optimal Parallel Routing in Star Networks
Star networks have recently been proposed as attractive alternatives to the popular hypercube for interconnecting processors on a parallel computer. In this paper, we present an efficient algorithm that constructs an optimal parallel routing in star networks. Our result improves previous results for the problem.
1021255
A minimal and complete set of operators for the development of robust manifold mesh modelers
In this paper, we identify a minimal and complete set of fundamental operators, which is necessary and sufficient for performing all homeomorphic and topological operations on 2- manifold mesh structures. Efficient algorithms are developed for the implementation of these operators. We also developed a set of powerful, user-friendly, and effective operators at the level of user-interface. Using these operators, we have developed a prototype system for robust, interactive, and user-friendly modeling of orientable 2-manifold meshes. Users of our system can perform a large set of homeomorphic and topological changes with these user-interface level operators. Our system is topologically robust in the sense that users will never create invalid 2-manifold mesh structure with these operators. In our system, the homeomorphic and topological surgery operations can be applied alternatively on 2-manifold meshes. With our system, users can blend surfaces, construct rinds, and open holes on these rind shapes. With our system, the shapes that look like solid, non-manifold, or 2-manifold with boundary can be manipulated. The system also provides automatic texture mapping during topology changes.
2261180
Graph Ear Decompositions and Graph Embeddings
Ear decomposition of a graph has been extensively studied in relation to graph connectivity. In this paper, a connection of ear decomposition to graph embeddings is exhibited. It is shown that constructing a maximum-paired ear decomposition of a graph and constructing a maximum-genus embedding of the graph are polynomial-time equivalent. Applications of this connection are discussed.
8059419
Asymptotic analysis of MIMO wireless systems with spatial correlation at the receiver
With a unified approach, this paper investigates the asymptotic performance or, equivalently, the large-system properties, of various point-to-point systems with antenna-array-based multiple-input multiple-output (MIMO) channels having spatial correlations. Using the replica method originally developed for statistical physics, we provide analytical solutions to the input-output mutual information of MIMO systems: 1) at the transmit side, with arbitrary inputs, and 2) at the receive side, with either the optimum space-time joint decoding or various suboptimum spatial equalizers followed by a bank of temporal decoders. Important physical meanings revealed though the analytical solutions to those more practical combinations, such as how the input-output mutual information is affected by the channel spatial correlations, are highlighted along our derivation. Moreover, we provide a novel waterfilling algorithm to determine the data-rate-maximizing transmit signal covariance matrix when only the channel long-term spatial correlations are available at the transmitter.
2587881
Isomap Based on the Image Euclidean Distance
Scientists find that the human perception is based on the similarity on the manifold of data set. Isometric feature mapping (isomap) is one of the representative techniques of manifold. It is intuitive, well understood and produces reasonable mapping results. However, if the input data for manifold learning are corrupted with noises, the isomap algorithm is topologically unstable. In this paper, we present an improved manifold learning method when the input data are images - the image Euclidean distance based isomap (imisomap), in which we use a new distance for images called image Euclidean distance (IMED). Experimental results demonstrate a consistent performance improvement of the algorithm imisomap over the traditional isomap based on Euclidean distance
6316461
Partitioned optimization algorithms for multiple sequence alignment
Multiple sequence alignment is an important and difficult problem in molecular biology and bioinformatics. In this paper, we propose a partitioning approach that significantly improves the solution time and quality by utilizing the locality structure of the problem. The algorithm solves the multiple sequence alignment in three stages. First, an automated and suboptimal partitioning strategy is used to divide the set of sequences into several subsections. Then a multiple sequence alignment algorithm based on ant colony optimization is used to align the sequences of each subsection. Finally, the alignment of original sequences can be obtained by assembling the result of each subsection. The ant colony algorithm is highly optimized in order to avoid local optimal traps and converge to global optimal efficiently. Experimental results show that the algorithm can significantly reduce the running time and improve the solution quality on large-scale multiple sequence alignment benchmarks.
1479779
Programming by demonstration: removing sub-optimal actions in a partially known configuration space
Programming by demonstration is a promising approach to automatic robot programming, however, methods are required to remove suboptimal actions that can be demonstrated by end users. In this paper we use the partial knowledge of configuration space (C-space) derived in the previous work by Chen et al. (2000) to remove suboptimal actions from a demonstration. Our idea is to use demonstrated paths to predict what regions in C-space are obstacle free. Suboptimal actions in a demonstration are then avoided by planning alternative actions that pass through the obstacle free regions. Experimental results show the validity of the approach. A demonstrated path containing significant sub-optimality was converted by the approach into a short, efficient path suitable for execution by the robot.
8954904
Modification of the AdaBoost-based Detector for Partially Occluded Faces
While face detection seems a solved problem under general conditions, most state-of-the-art systems degrade rapidly when faces are partially occluded by other objects. This paper presents a solution to detect partially occluded faces by reasonably modifying the AdaBoost-based face detector. Our basic idea is that the weak classifiers in the AdaBoost-based face detector, each corresponding to a Haar-like feature, are inherently a patch-based model. Therefore, one can divide the whole face region into multiple patches, and map those weak classifiers to the patches. The weak classifiers belonging to each patch are re-formed to be a new classifier to determine if it is a valid face patch - without occlusion. Finally, we combine all of the valid face patches by assigning the patches with different weights to make the final decision whether the input subwindow is a face. The experimental results show that the proposed method is promising for the detection of occluded faces