An improved exact algorithm for the domatic number problem

The 3-domatic number problem asks whether a given graph can be partitioned into three dominating sets. We prove that this problem can be solved by a deterministic algorithm in time n^2.695 (up to polynomial factors) and in polynomial space. This result improves the previous bound of n^2.8805, which is due to Björklund and Husfeldt. To prove our result, we combine an algorithm by Fomin et al. with Yamamoto's algorithm for the satisfiability problem. In addition, we show that the 3-domatic number problem can be solved for graphs G with bounded maximum degree Δ(G) by a randomized polynomial-space algorithm, whose running time is better than the previous bound due to Riege and Rothe whenever Δ(G)?5. Our new randomized algorithm employs Schöning's approach to constraint satisfaction problems.     

PID controller design using double helix structured DNA algorithms with a recovery function

PID controllers have been widely used in industrial fields. Since the PID parameters have a great influence on the stability and performance of the control system, many approaches have been proposed to determine them. In this article, we propose double helix structured DNA algorithms to design the type of PID controller and optimize the PID parameters. The double helix structured DNA algorithms employ a DNA encoding method based on a base-64 notational system to represent the PID parameters, define various mutation methods, and have a recovery function to preserve a DNA strand that has good fitness value. A computer simulation shows that we can get satisfactory results with the proposed method. This work was presented in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January 25–27, 2007     

An improved approximation ratio for the minimum linear arrangement problem

We observe that combining the techniques of Arora, Rao, and Vazirani, with the rounding algorithm of Rao and Richa yields an -approximation for the minimum-linear arrangement problem. This improves over the O(logn)-approximation of Rao and Richa.     

Prediction of beef eating qualities from colour, marbling and wavelet surface texture features using homogenous carcass treatment

Colour, marbling and surface texture properties of beef longissimus dorsi muscle are used in some countries to grade carcasses according to their expected eating quality. Handheld VIA systems are being used to augment the grader assessments, however attempts have been made to develop higher resolution image systems to give consistent and objective predictions of quality based on these properties. Previous efforts have been unable to model sufficiently the variation in eating quality. A new approach has been applied whereby beef carcasses were subjected to homogenous post-slaughter treatment to minimize variation in eating quality related to other factors such as chilling temperature and hanging method. Furthermore a wider range of features were used to better characterize colour and marbling and the wavelet transform was used to characterize texture. Objective and sensory panel tests were performed to evaluate the beef eating qualities. Classical statistical methods of multilinear regression (MLR) and partial least squares regression (PLSR) were used to develop predictive models. It was possible to explain a greater portion of variation in eating quality than before (up to r²=0.83). Carcasses were classified as high or low quality with a high rate of correct classifications (90%). Genetic algorithms were used to select the model subsets.     

An improved parallel algorithm for integer GCD

We present a simple parallel algorithm for computing the greatest common divisor (gcd) of twon-bit integers in the Common version of the CRCW model of computation. The run-time of the algorithm in terms of bit operations isO(n/logn), usingn ¹⁺ processors, where is any positive constant. This improves on the algorithm of Kannan, Miller, and Rudolph, the only sublinear algorithm known previously, both in run time and in number of processors; they requireO(n log logn/logn),n ² log² n, respectively, in the same CRCW model.We give an alternative implementation of our algorithm in the CREW model. Its run-time isO(n log logn/logn), usingn ¹⁺ processors. Both implementations can be modified to yield the extended gcd, within the same complexity bounds.Supported in part by an IBM Graduate Fellowship and a Bantrell Postdoctoral Fellowship.Supported in part by a Weizmann Postdoctoral Fellowship.4 All logarithms are to base 2.     

Analysis of colour channel coupling from a physics-based viewpoint: Application to colour edge detection

The Dichromatic Reflection Model (DRM) introduced by Shafer in 1985 is surely the most referenced physics-based model of image formation. A preliminary analysis of this model derives in the conclusion that colour channels remain coupled by the reflectance of objects surface material. Taking this observation as a basis, this paper shows that this coupling manifests itself at the signal level in the form of a set of properties only satisfied in uniform reflectance areas. Such properties are deeply analysed and formalized throughout the paper, and, eventually, they are stated geometrically. As will be seen, a compatibility relationship stems from this geometric interpretation, which allows checking at a very low cost whether two pixels correspond to the same scene reflectance or not. Finally, an edge detector based on the use of the previous relationship is presented as an example of application. This edge detector inherits all the properties of the compatibility relationship: simplicity, low computational power requirements, sensor noise adaptivity and insensitivity to image intensity changes due to scene objects curvature.     

An improved kernelization algorithm for r-Set Packing

We present a reduction procedure that takes an arbitrary instance of the r-Set Packing problem and produces an equivalent instance whose number of elements is in O(kr−1), where k is the input parameter. Such parameterized reductions are known as kernelization algorithms, and a reduced instance is called a problem kernel. Our result improves on previously known kernelizations by a factor of k. In particular, the number of elements in a 3-Set Packing kernel is improved from a cubic function of the parameter to a quadratic one.     

The effect of brightness on colour recognition under water

Abstract

Water distorts the colours of objects compared to the situation in air, and it is relevant to enquire how this affects divers' colour recognition. Twelve divers (eight in the laboratory and four in a field experiment) were required to determine the distances at which colours could be correctly identified in different types of water. Changing a target's brightness (keeping hue and saturation constant) significantly changed its recognition distance. In addition, reducing the reflectance of a target having a similar hue to that of the background reduced its recognition distance relatively more than targets with hues offset from that of the background. Consequently, classification by hue name alone was insufficient to allow an unambiguous rank ordering of the relative recognition distances of the different colours. In situ light measurements in the field study permitted the specification of the spectral characteristics of the targets and their visual background. Such data are important if a colour recognition model is to be established for situations involving gross spectral distortion.     

Adaptive fusion of particle filtering and spatio-temporal motion energy for human tracking

Object tracking is an active research area nowadays due to its importance in human computer interface, teleconferencing and video surveillance. However, reliable tracking of objects in the presence of occlusions, pose and illumination changes is still a challenging topic. In this paper, we introduce a novel tracking approach that fuses two cues namely colour and spatio-temporal motion energy within a particle filter based framework. We conduct a measure of coherent motion over two image frames, which reveals the spatio-temporal dynamics of the target. At the same time, the importance of both colour and motion energy cues is determined in the stage of reliability evaluation. This determination helps maintain the performance of the tracking system against abrupt appearance changes. Experimental results demonstrate that the proposed method outperforms the other state of the art techniques in the used test datasets.     

An improved algorithm for finding the median distributively

Given two processes, each having a total-ordered set ofn elements, we present a distributed algorithm for finding median of these 2n elements using no more than logn +O(logn) messages, but if the elements are distinct, only logn +O(1) messages will be required. The communication complexity of our algorithm is better than the previously known result which takes 2 logn messages.     

机器视觉在光纤缺陷检测中的应用

目前,光纤已广泛应用于通信领域。光纤连接器作为精密对接光纤两个端面的部件,其重要性不言而喻,传统的端面检测方法是以人工方式对光纤显微镜下的图像是否合格进行判断,不仅精度低,而且效率低下,而利用机器视觉,由计算机来检验可以很好地解决这个问题。     

Extensive experiments with hybrid genetic algorithms for the solution of the quadratic assignment problem

In this paper we perform extensive computational experiments solving quadratic assignment problems using various variants of a hybrid genetic algorithm. We introduce a new tabu search (simple tabu). We compared the modified robust tabu and the simple tabu as improvement algorithms in a hybrid genetic algorithm with other tabu searches (concentric tabu, ring moves, all moves, robust tabu) with superior results. We also tested several modifications of the hybrid genetic algorithm and all of them produced good results.     

An improved FPTAS for Restricted Shortest Path

Given a graph with a cost and a delay on each edge, Restricted Shortest Path (RSP) aims to find a min-cost s-t path subject to an end-to-end delay constraint. The problem is NP-hard. In this note we present an FPTAS with an improved running time of O(mn/ε) for acyclic graphs, where m and n denote the number of edges and nodes in the graph. Our algorithm uses a scaling and rounding technique similar to that of Hassin [Math. Oper. Res. 17 (1) (1992) 36-42]. The novelty of our algorithm lies in its “adaptivity”. During each iteration of our algorithm the approximation parameters are fine-tuned according to the quality of the current solution so that the running time is kept low while progress is guaranteed at each iteration. Our result improves those of Hassin [Math. Oper. Res. 17 (1) (1992) 36-42], Phillips [Proc. 25th Annual ACM Symposium on the Theory of Computing, 1993, pp. 776-785], and Raz and Lorenz [Technical Report, 1999].     

An improved lower bound on approximation algorithms for the Closest Substring problem

The Closest Substring problem (the CSP problem) is a basic NP-hard problem in the study of computational biology. It is known that the problem has polynomial time approximation schemes. In this paper, we prove that unless the Exponential Time Hypothesis fails, the CSP problem has no polynomial time approximation schemes of running time f(1/ε)n^o(1/ε) for any function f. This essentially excludes the possibility that the CSP problem has a practical polynomial time approximation scheme even for moderate values of the error bound ε. As a consequence, it is unlikely that the study of approximation schemes for the CSP problem in the literature would lead to practical approximation algorithms for the problem for small error bound ε.     

Indexing chromatic and achromatic patterns for content-based colour image retrieval

In this paper, we present a method to represent achromatic and chromatic image signals independently for content-based image indexing and retrieval for image database applications. Starting from an opponent colour representation, human colour vision theories and modern digital signal processing technologies are applied to develop a compact and computationally efficient visual appearance model for coloured image patterns. We use the model to compute the statistics of achromatic and chromatic spatial patterns of colour images for indexing and content-based retrieval. Two types of colour images databases, one colour texture database and another photography colour image database are used to evaluate the performance of the developed method in content-based image indexing and retrieval. Experimental results are presented to show that the new method is superior or competitive to state-of-the-art content-based image indexing and retrieval techniques.     

Almost 2-SAT is fixed-parameter tractable

We consider the following problem. Given a 2-cnf formula, is it possible to remove at most k clauses so that the resulting 2-cnf formula is satisfiable? This problem is known to different research communities in theoretical computer science under the names Almost 2-SAT, All-but-k 2-SAT, 2-cnf deletion, and 2-SAT deletion. The status of the fixed-parameter tractability of this problem is a long-standing open question in the area of parameterized complexity. We resolve this open question by proposing an algorithm that solves this problem in O(k¹⁵×k×m³) time showing that this problem is fixed-parameter tractable.     

An improved algorithm for online coloring of intervals with bandwidth

We present an improved online algorithm for coloring interval graphs with bandwidth. This problem has recently been studied by Adamy and Erlebach and a 195-competitive online strategy has been presented. We improve this by presenting a 10-competitive strategy. To achieve this result, we use variants of an optimal online coloring algorithm due to Kierstead and Trotter.     

An improved approximation algorithm for the metric maximum clustering problem with given cluster sizes

The input to the metric maximum clustering problem with given cluster sizes consists of a complete graph G=(V,E) with edge weights satisfying the triangle inequality, and integers c₁,…,cp. The goal is to find a partition of V into disjoint clusters of sizes c₁,…,cp, maximizing the sum of weights of edges whose two ends belong to the same cluster. We describe an approximation algorithms for this problem with performance guarantee that approaches 0.5 when the cluster sizes are large.     

An improved GA and a novel PSO-GA-based hybrid algorithm

Inspired by the natural features of the variable size of the population, we present a variable population-size genetic algorithm (VPGA) by introducing the “dying probability” for the individuals and the “war/disease process” for the population. Based on the VPGA and the particle swarm optimization (PSO) algorithms, a novel PSO-GA-based hybrid algorithm (PGHA) is also proposed in this paper. Simulation results show that both VPGA and PGHA are effective for the optimization problems.     

An improved upperbound for distributed election in bidirectional rings of processors

We present a distributed algorithm for electing a leader (i. e., breaking symmetry) in bidirectional rings ofN processors with no global sense of orientation, that uses at most 1.44 ...N logN+O(N) messages in the worst case.Jan van Leeuwen received his M. Sc. degree in 1969 (cum laude) and the Ph.D. degree in 1972 from the University of Utrecht, Utrecht, The Netherlands. He held a postdoctorate fellowship in computer science at the University of California at Berkeley (1972–1973), visiting assistant professorship in computer science at the State University of New York at Buffalo (1973–1974, 1975–1976), and a visiting associate professorship in computer science at The Pennsylvania State University, University Park (1976–1977). In 1977 he was appointed Associate Professor of Computer Science at the University of Utrecht and became head of the new Department of Computer Science at this university. He is presently Full Professor of Computer Science. Dr. van Leeuwen is active in many disciplines within computer science. His primary research interests are fundamental studies in varied areas of computer science, viz. the analysis and complexity of computer algorithms, in both a theoretical and an applied sense (e. g. data structures, machine models, VLSI, parallel and distributed computing, and cryptography).Richard B. Tan is an Associate Professor of Mathematics and Computer Science at the University of Sciences and Arts of Oklahoma. He spends his summers at the University of Utrecht, the Netherlands. His research interests are in distributed computation and graph algorithms. He received the B. Sc. in Physics from Beloit College, WI., the M.S. in Computer Science and the Ph.D. (in 1980) in Mathematics from the University of Oklahoma.This work was done while the second author was visiting the University of Utrecht, supported by a grant of the Netherlands Organization for the Advancement of Pure Research (ZWO)