Search

A semi-matching in a bipartite graph $$G = (U, V, E)$$ is a set of edges $$M \subseteq E$$ such that each vertex in U is incident to exactly one edge in M, i.e., $$deg_M(u)=1$$ for each $$u \in U$$ . An optimal semi-matching is a semi-matching with the minimal value of the cost function $$\sum _{v \in V} \frac{deg_M(v) \cdot (deg_M(v)+1)}{2}$$ . Exploiting the divide-and-conquer nature of the semi-matching problem, we reduce the problem to a simpler problem whose objective is to compute a maximum weak bounded-degree semi-matching. Using the reduction we derive three algorithms for the optimal semi-matching problem. The first one runs in time $$O(\sqrt{n} \cdot m \cdot \log {n})$$ on a graph with n vertices and m edges. The second one is randomized and computes an optimal semi-matching with high probability in time $$O(n^{\omega } \cdot \log ^{1+o(1)} n)$$ , where $$\omega $$ is the exponent of the best known matrix multiplication algorithm. Since $$\omega < 2.38$$ , this algorithm breaks through $$O(n^{2.5})$$ barrier for dense graphs. In the case of planar graphs, the third one computes an optimal semi-matching in deterministic time $$O(n\cdot \log ^4{n})$$ . [ABSTRACT FROM AUTHOR]

We present a new overlay, called the Deterministic Decentralized tree ( $$D^2$$ -tree). The $$D^2$$ -tree compares favorably to other overlays for the following reasons: (a) it provides matching and better complexities, which are deterministic for the supported operations; (b) the management of nodes (peers) and elements are completely decoupled from each other; and (c) an efficient deterministic load-balancing mechanism is presented for the uniform distribution of elements into nodes, while at the same time probabilistic optimal bounds are provided for the congestion of operations at the nodes. The load-balancing scheme of elements into nodes is deterministic and general enough to be applied to other hierarchical tree-based overlays. This load-balancing mechanism is based on an innovative lazy weight-balancing mechanism, which is interesting in its own right. [ABSTRACT FROM AUTHOR]