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/

Zendy Plus

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

Zendy Tools

Zendy Open

This paper shows the weighted matching problem on general graphs can besolved in time $O(n(m + n\log n))$ for $n$ and $m$ the number of vertices andedges, respectively. This was previously known only for bipartite graphs. Thecrux is a data structure for blossom creation. It uses a dynamicnearest-common-ancestor algorithm to simplify blossom steps, so they involveonly back edges rather than arbitrary nontree edges.  The rest of the paper presents direct extensions of Edmonds' blossomalgorithm to weighted $b$-matching and $f$-factors. Again the time bound is theone previously known for bipartite graphs: for $b$-matching the time is$O(\min\{b(V),n\log n\}(m + n\log n))$ and for $f$-factors the time is$O(\min\{f(V),m\log n\}( m + n\log n) )$, where $b(V)$ and $f(V)$ denote thesum of all degree constraints. Several immediate applications of the $f$-factoralgorithm are given: The generalized shortest path structure of \cite{GS13},i.e., the analog of the shortest path tree for conservative undirected graphs,is shown to be a version of the blossom structure for $f$-factors. Thisstructure is found in time $O(|N|(m+n\log n))$ for $N$ the set of negativeedges ($0<|N|<n$). A shortest $T$-join is found in time $O(n(m+n\log n))$, or$O(|T|(m+n\log n))$ when all costs are nonnegative. These bounds are all slightimprovements of previously known ones, and are simply achieved by properinitialization of the $f$-factor algorithm.

Data Structures for Weighted Matching and Extensions to $b$-matching and $f$-factors