An addendum on the incremental assignment problem

In Toroslu and Üçoluk [I.H. Toroslu, G. Üçoluk, Incremental assignment problem, Information Sciences 177 (2007) 1523-1529] the incremental assignment problem is defined as follows. A new pair of vertices and their incident edges are added to a weighted bipartite graph whose maximum-weighted matching is already known, and the maximum-weighted matching of the extended graph is sought. An O(n²) algorithm for the problem has been derived, with n the size of a partition in the bipartite graph. We point out that such a result can be found in literature.     

Approximate minimum weight matching on points ink-dimensional space

We study the problem of finding a minimum weight complete matching in the complete graph on a set V ofn points ink-dimensional space. The points are the vertices of the graph and the weight of an edge between any two points is the distance between the points under someL _q,-metric. We give anO((2c _q )^1.5k ?^?1.5k (α(n, n))^0.5 n ^1.5(logn)^2.5) algorithm for finding an almost minimum weight complete matching in such a graph, wherec _q =6k ^1/q for theL _q -metric, α is the inverse Ackermann function, and ? ≤ 1. The weight of the complete matching obtained by our algorithm is guaranteed to be at most (1 + ?) times the weight of a minimum weight complete matching.     

Almost Exact Matchings

In the exact matching problem we are given a graph G, some of whose edges are colored red, and a positive integer k. The goal is to determine if G has a perfect matching, exactly k edges of which are red. More generally if the matching number of G is m=m(G), the goal is to find a matching with m edges, exactly k edges of which are red, or determine that no such matching exists. This problem is one of the few remaining problems that have efficient randomized algorithms (in fact, this problem is in RNC), but for which no polynomial time deterministic algorithm is known. Our first result shows that, in a sense, this problem is as close to being in P as one can get. We give a polynomial time deterministic algorithm that either correctly decides that no maximum matching has exactly k red edges, or exhibits a matching with m(G)?1 edges having exactly k red edges. Hence, the additive error is one. We also present an efficient algorithm for the exact matching problem in families of graphs for which this problem is known to be tractable. We show how to count the number of exact perfect matchings in K _3,3-minor free graphs (these include all planar graphs as well as many others) in O(n ^3.19) worst case time. Our algorithm can also count the number of perfect matchings in K _3,3-minor free graphs in O(n ^2.19) time.     

Image interpretation with a conceptual graph: Labeling over-segmented images and detection of unexpected objects

The labeling of the regions of a segmented image according to a semantic representation (ontology) is usually associated with the notion of understanding. The high combinatorial aspect of this problem can be reduced with local checking of constraints between the elements of the ontology. In the classical definition of Finite Domain Constraint Satisfaction Problem, it is assumed that the matching problem between regions and labels is bijective. Unfortunately, in image interpretation the matching problem is often non-univocal. Indeed, images are often over-segmented: one object is made up of several regions. This non-univocal matching between data and a conceptual graph was not possible until a decisive step was accomplished by the introduction of arc consistency with bilevel constraint (FDCSPBC). However, this extension is only adequate for a matching corresponding to surjective functions. In medical image analysis, the case of non-functional relations is often encountered, for example, when an unexpected object like a tumor appears. In this case, the data cannot be mapped to the conceptual graph, with a classical approach. In this paper we propose an extension of the FDCSPBC to solve the constraint satisfaction problem for non-functional relations.     

The general maximum matching algorithm of micali and vazirani

We give a clear exposition of the algorithm of Micali and Vazirani for computing a maximum matching in a general graph. This is the most efficient algorithm known for general matching. On a graph withn vertices andm edges this algorithm runs inO(n ^1/2 m) time.     

A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2

The maximum weight matching problem is a fundamental problem in graph theory with a variety of important applications. Recently Manne and Mjelde presented the first self-stabilizing algorithm computing a 2-approximation of the optimal solution. They established that their algorithm stabilizes after O(2ⁿ) (resp. O(3ⁿ)) moves under a central (resp. distributed) scheduler. This paper contributes a new analysis, improving these bounds considerably. In particular it is shown that the algorithm stabilizes after O(nm) moves under the central scheduler and that a modified version of the algorithm also stabilizes after O(nm) moves under the distributed scheduler. The paper presents a new proof technique based on graph reduction for analyzing the complexity of self-stabilizing algorithms.     

Path-matching problems

The notion of matching in graphs is generalized in this paper to a set of paths rather than to a set of edges. The generalized problem, which we call thepath-matching problem, is to pair the vertices of an undirected weighted graph such that the paths connecting each pair are subject to certain objectives and/or constraints. This paper concentrates on the case where the paths are required to be edge-disjoint and the objective is to minimize the maximal cost of a path in the matching (i.e., the bottleneck version). Other variations of the problem are also mentioned. Two algorithms are presented to find the best matching under the constraints listed above for trees. Their worst-case running times areO(n logd logw), whered is the maximal degree of a vertex,w is the maximal cost of an edge, andn is the size of the tree, andO(n ²), respectively. The problem is shown to be NP-complete for general graphs. Applications of these problems are also discussed.     

Solving the Euclidean bottleneck matching problem byk-relative neighborhood graphs

Given a set of pointsV in the plane, the Euclidean bottleneck matching problem is to match each point with some other point such that the longest Euclidean distance between matched points, resulting from this matching, is minimized. To solve this problem, we definek-relative neighborhood graphs, (kRNG) which are derived from Toussaint's relative neighborhood graphs (RNG). Two points are calledk-relative neighbors if and only if there are less thank points ofV which are closer to both of the two points than the two points are to each other. AkRNG is an undirected graph (V,E _r ^k ) whereE _r ^k is the set of pairs of points ofV which arek-relative neighbors. We prove that there exists an optimal solution of the Euclidean bottleneck matching problem which is a subset ofE _r ¹⁷ . We also prove that ¦E _r ^k ¦ < 18kn wheren is the number of points in setV. Our algorithm would construct a 17RNG first. This takesO(n ²) time. We then use Gabow and Tarjan's bottleneck maximum cardinality matching algorithm for general graphs whose time-complexity isO((n logn)^0.5 m), wherem is the number of edges in the graph, to solve the bottleneck maximum cardinality matching problem in the 17RNG. This takesO(n ^1.5 log^0.5 n) time. The total time-complexity of our algorithm for the Euclidean bottleneck matching problem isO(n ² +n ^1.5 log^0.5 n).     

An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs

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(n²logn)-time algorithm, where n is the number of vertices of the input graph. In fact, the O(n²logn)-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(n²logn) 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.     

Finding a dominating set on bipartite graphs

Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O^∗(²n−z), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O^∗(²n/2). Another implication is an algorithm for general graphs whose running time is O(n^1.7088).