A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is an evidence that can be used to authenticate the correctness of the answer. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appears exactly once. The Hamiltonian cycle problem is to determine whether or not a graph contains a Hamiltonian cycle. The best result for the Hamiltonian cycle problem on circular-arc graphs is an O(n2logn)-time algorithm, where n is the number of vertices of the input graph. In fact, the O(n2logn)-time algorithm can be modified as a certifying algorithm although it was published before the term certifying algorithms appeared in the literature. However, whether there exists an algorithm whose time complexity is better than O(n2logn) for solving the Hamiltonian cycle problem on circular-arc graphs has been opened for two decades. In this paper, we present an O(Δn)-time certifying algorithm to solve this problem, where Δ represents the maximum degree of the input graph. The certificates provided by our algorithm can be authenticated in O(n) time.

The major problem of SVMs is the dependence of the nonlinear separating surface on the entire dataset which creates unwieldy storage problems. This paper proposes a novel design algorithm, called the extractive support vector algorithm, which provides improved learning speed and a vastly improved performance. Instead of learning and training with all input patterns, the proposed algorithm selects support vectors from the input patterns and uses these support vectors as the training patterns. Experimental results reveal that our proposed algorithmprovides near optimal solutions and outperforms the existing design algorithms. In addition, a significant framework which is based on extractive support vector algorithm is proposed for image restoration. In the framework, input patterns are classified by three filters: weighted order statistics filter, alpha-trimmed mean filter and identity filter. Our proposed filter can achieve three objectives: noise attenuation, chromaticity retention, and preservation of edges and details. Extensive simulation results illustrate that our proposed filter not only achieves these three objectives but also possesses robust and adaptive capabilities, and outperforms other proposed filtering techniques.