English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $G$ be an undirected bipartite graph with positive integer weights on theedges. We refine the existing decomposition theorem originally proposed by Kaoet al., for computing maximum weight bipartite matching. We apply it to designan efficient version of the decomposition algorithm to compute the weight of amaximum weight bipartite matching of $G$ in $O(\sqrt{|V|}W'/k(|V|,W'/N))$-timeby employing an algorithm designed by Feder and Motwani as a subroutine, where$|V|$ and $N$ denote the number of nodes and the maximum edge weight of $G$,respectively and $k(x,y)=\log x /\log(x^2/y)$. The parameter $W'$ is smallerthan the total edge weight $W,$ essentially when the largest edge weightdiffers by more than one from the second largest edge weight in the currentworking graph in any decomposition step of the algorithm. In best case$W'=O(|E|)$ where $|E|$ be the number of edges of $G$ and in worst case $W'=W,$that is, $|E| \leq W' \leq W.$ In addition, we talk about a scaling property ofthe algorithm and research a better bound of the parameter $W'$. Anexperimental evaluation on randomly generated data shows that the proposedimprovement is significant in general.

Experimental Evaluation of Modified Decomposition Algorithm for Maximum Weight Bipartite Matching