For a graph G=(V,E), finding a set of disjoint edges that do not share any vertices is called a matching problem, and finding the maximum matching is a fundamental problem in the theory of distributed graph algorithms. Although local algorithms for the approximate maximum matching problem have been widely studied, exact algorithms have not been much studied. In fact, no exact maximum matching algorithm that is faster than the trivial upper bound of O(n2) rounds is known for general instances. In this paper, we propose a randomized $O(s_{max}^{3/2})$-round algorithm in the CONGEST model, where smax is the size of maximum matching. This is the first exact maximum matching algorithm in o(n2) rounds for general instances in the CONGEST model. The key technical ingredient of our result is a distributed algorithms of finding an augmenting path in O(smax) rounds, which is based on a novel technique of constructing a sparse certificate of augmenting paths, which is a subgraph of the input graph preserving at least one augmenting path. To establish a highly parallel construction of sparse certificates, we also propose a new characterization of sparse certificates, which might also be of independent interest.

Efficient parallel algorithms for several problems on proper circular arc graphs are presented in this paper. These problems include finding a maximum matching, partitioning into a minimum number of induced subgraphs each of which has a Hamiltonian cycle (path), partitioning into induced subgraphs each of which has a Hamiltonian cycle (path) with at least k vertices for a given k, and adding a minimum number of edges to make the graph contain a Hamiltonian cycle (path). It is shown here that the above problems can all be solved in logarithmic time with a linear number of EREW PRAM processors, or in constant time with a linear number of BSR processors. A more important part of this work is perhaps the extension of basic BSR to allow simultaneous multiple BROADCAST instructions.

The Minimum Covering Run (MCR) expression used for representing binary images has been proposed [1]-[3]. The MCR expression is an adaptation from horizontal and vertical run expression. In the expression, some horizontal and vertical runs are used together for representing binary images in which total number of them is minimized. It was shown that, sets of horizontal and vertical runs representing any binary image could be viewed as partite sets of a bipartite graph, then the MCR expression of binary images was found analogously by constructing a maximum matching as well as a minimum covering in the corresponding graph. In the original algorithm, the most efficient algorithm, proposed by Hopcroft, solving the graph-theoretical problems mentioned above, associated with the Rectangular Segment Analysis (RSA) was used for finding the MCR expression. However, the original algorithm still suffers from a long processing time. In this paper, we propose two new efficient MCR algorithms that are beneficial to a practical implementation. The new algorithms are composed of two main procedures; i.e., Partial Segment Analysis (PSA) and construction of a maximum matching. It is shown in this paper that the first procedure which is directly an improvement to the RSA, appoints well a lot of representative runs of the MCR expression in regions of text and line drawing. Due to the PSA, the new algorithms reduce the number of runs used in the technique of solving the matching problem in corresponding graphs so that satisfactory processing time can be obtained. To clarify the validity of new algorithms proposed in this paper, the experimental results show the comparative performance of the original and new algorithms in terms of processing time.

An efficient technique for expressing document image is required as part of a unified approach to document image processing. This paper presents a new method, Minimum Covering Run (MCR), for expressing binary images. The name being adapted from horizontal or vertical run representation. The proposed technique uses some horizontal and vertical runs together to represent binary images in which the total number of representative runs is minimized. Considering the characteristic of above run types precisely, it is shown that horizontal and vertical runs of any binary image could be thought of as partite sets of a bipartite graph. Consequently, the MCR expression that corresponds to the construction of one of the most interesting problems in graphs; i.e., maximum matching, is analogously found by using an algorithm which solves this problem in a corresponding graph. The most efficient algorithm takes at most O(n5/2) computations for solving the problem where n is the sum of cardinalities of both partite sets. However, some patterns in images like tables or line drowings, generally, have a large number of runs representing them which results in a long processing time. Therefore, we provide the Rectangular Segment Analysis (RSA) as a pre-processing to define runs representing such patterns beforehand. We also show that horizontal and vertical covering parts of the proposed expression are able to represent stroke components of characters in document images. As an implementation, an efficient algorithm including arrangement for run data structure of the MCR expression is presented. The experimental results show the possibility of stroke extraction of characters in document images. As an application, some patterns such as tables can be extracted from document images.