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

We prove an exact lower bound on $\gamma(G)$, the size of the smallest matching that a certain $O(m+n)$ time greedy matching procedure may find for a given graph $G$ with $n$ vertices and $m$ edges. The bound is precisely Erdős and Gallai's extremal function that gives the size of the smallest maximum matching, over all graphs with $n$ vertices and $m$ edges. Thus the greedy procedure is optimal in the sense that when only $n$ and $m$ are specified, no algorithm can be guaranteed to find a larger matching than the greedy procedure. The greedy procedure and augmenting path algorithms are seen to be complementary: the greedy procedure finds a large matching for dense graphs, while augmenting path algorithms are fast for sparse graphs. Well known hybrid algorithms consisting of the greedy procedure followed by an augmenting path algorithm are shown to be faster than the augmenting path algorithm alone. The lower bound on $\gamma(G)$ is a stronger version of Erdős and Gallai's result, and so the proof of the lower bound is a new way of proving of Erdős and Gallai's result.

An Exact Performance Bound for an ${O (m+n)}$ Time Greedy Matching Procedure