Solving the Maximum Matching Problem on Bipartite Star123-Free Graphs in Linear Time

The bipartite Star123-free graphs were introduced by V. Lozin in [1] to generalize some already known classes of bipartite graphs. In this paper, we extend to bipartite Star123-free graphs a linear time algorithm of J. L. Fouquet, V. Giakoumakis and J. M. Vanherpe for finding a maximum matching in bipartite Star123, P7-free graphs presented in [2]. Our algorithm is a solution of Lozin’s conjecture.

An Algorithm for the Feedback Vertex Set Problem on a Normal Helly Circular-Arc Graph

The feedback vertex set (FVS) problem is to find the set of vertices of minimum cardinality whose removal renders the graph acyclic. The FVS problem has applications in several areas such as combinatorial circuit design, synchronous systems, computer systems, and very-large-scale integration (VLSI) circuits. The FVS problem is known to be NP-hard for simple graphs, but polynomi-al-time algorithms have been found for special classes of graphs. The intersection graph of a collection of arcs on a circle is called a circular-arc graph. A normal Helly circular-arc graph is a proper subclass of the set of circular-arc graphs. In this paper, we present an algorithm that takes time to solve the FVS problem in a normal Helly circular-arc graph with n vertices and m edges.

Engineering the Divide-and-Conquer Closest Pair Algorithm

We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle-packing property, computes at most 7n/2 Euclidean distances, which improves Ge et al.＇s bound of （3n log n）/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.

Optimal Routing in a Small-World Network

Substantial research has been devoted to the modelling of the small-world phenomenon that arises in nature as well as human society. Earlier work has focused on the static properties of various small-world models. To examine the routing aspects, Kleinberg proposes a model based on a d-dimensional toroidal lattice with long-range links chosen at random according to the d-harmonic distribution. Kleinberg shows that, by using only local information, the greedy routing algorithm performs in O（lg^2 n） expected number of hops. We extend Kleinberg＇s small-world model by allowing each node x to have two more random links to nodes chosen uniformly and randomly within （lg n）2/d Manhattan distance from x. Based on this extended model, we then propose an oblivious algorithm that can route messages between any two nodes in O（lg n） expected number of hops. Our routing algorithm keeps only O（（lgn）β＋1） bits of information on each node, where 1 〈 β 〈 2, thus being scalable w.r.t, the network size. To our knowledge, our result is the first to achieve the optimal routing complexity while still keeping a poly-logarithmic number of bits of information stored on each node in the small-world networks.

An Improved HEAPSORT Algorithm with nlogn-0.788928n Comparisons in the Worst Case

A new variant of HEAPSORT is presented in this paper. The algorithm is not an internal sorting algorithm in the strong sense, since extra storage for n integers is necessary. The basic idea of the new algorithm is similar to the classical sorting algorithm HEAPSORT, but the algorithm rebuilds the heap in another way. The basic idea of the new algorithm is it uses only one comparison at each node. The new algorithm shift walks down a path in the heap until a leaf is reached. The request of placing the element in the root immediately to its destination is relaxed. The new algorithm requires about n log n - 0.788928n comparisons in the worst case and n log n - n comparisons on the average which is only about 0.4n more than necessary. It beats on average even the clever variants of QUICKSORT, if n is not very small. The difference between the worst case and the best case indicates that there is still room for improvement of the new algorithm by constructing heap more carefully.

A Better Semi-online Algorithm for Q3/s_1=s_2≤s_3/C_(min) with the Known Largest Size

This paper investigates the semi-online machine covering problem on three special uniform machines with the known largest size. Denote by sj the speed of each machine, j = 1, 2, 3. Assume 0 〈 s1 = s2 = r 〈 t = s3, and let s = t/r be the speed ratio. An algorithm with competitive ratio max（2, 3s＋6/s＋6 is presented. We also show the lower bound is at least max（2, 38 3s/s＋6）. For s ≤ 6, the algorithm is an optimal algorithm with the competitive ratio 2. Besides, its overall competitive ratio is 3 which matches the overall lower bound. The algorithm and the lower bound in this paper improve the results of Luo and Sun.

On k-Positive Satisfiability Problem

An algorithm for solving the satisfiability problem is presented. It isproceed that this algorithm solves 2-SAT and Horn-SAT in linear time and k-positiveSAT (in which every clause contains at most k positive literals) ill time O(F.),where F is the length of input F, n is the number of atoms occurring in F, and k isthe greatest real number satisfying the equation x = 2-. Compared with previousresults, this nontrivial upper bound on time complexity could only be obtained fork-SAT, which is a subproblem of k-positive SAT.