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 present a quasi linear-time algorithm for Maximum Matching ondistance-hereditary graphs and some of their generalizations. This improves on[Dragan, WG'97], who proposed such an algorithm for the subclass of(tent,hexahedron)-free distance-hereditary graphs. Furthermore, our result isderived from a more general one that is obtained for b-Matching. In the (unitcost) b-Matching problem, we are given a graph G = (V, E) together with anonnegative integer capacity b v for every vertex v $\in$ V. The objective isto assign nonnegative integer weights (x e) e$\in$E so that: for every v $\in$V the sum of the weights of its incident edges does not exceed b v , ande$\in$E x e is maximized. We present the first algorithm for solving b-Matchingon cographs, distance-hereditary graphs and some of their generalizations inquasi linear time. For that, we use a decomposition algorithm that outputs forany graph G a collection of subgraphs of G with no edge-cutsets inducing acomplete bipartite subgraph (a.k.a., splits). The latter collection issometimes called a split decomposition of G. Furthermore, there exists ageneric method in order to design graph algorithms based on split decomposition[Rao, DAM'08]. However, this technique only applies to "localized" problems:for which a "best" partial solution for any given subgraph in a splitdecomposition can be computed almost independently from the remaining of thegraph. Such framework does not apply to matching problems since an augmentingpath may cross the subgraphs arbitrarily. We introduce a new technique thatsomehow captures all the partial solutions for a given union of subgraphs in asplit decomposition, in a compact and amenable way for algorithms - assumingsome piecewise linear assumption holds on the value of such solutions. Thelatter assumption is shown to hold for b-Matching. Doing so, we prove thatsolving b-Matching on any pair G, b can be reduced in quasi linear-time tosolving this problem on a collection of smaller graphs: that are obtained fromthe subgraphs in any split decomposition of G by replacing every vertex with aconstant-size module. In particular, if G has a split decomposition where allsubgraphs have order at most a fixed k, then we can solve b-Matching for G, bin O((k log 2 k)$\times$(m+n)$\times$log ||b|| 1)-time. This answers an openquestion of [Coudert et al., SODA'18].

A quasi linear-time b-Matching algorithm on distance-hereditary graphs and bounded split-width graphs