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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In the Maximum Subset Matching problem, which generalizesthe maximum matching problem, we are given a graph G = (V,E)and S ⊂ V. The goal is to determine the maximum number of verticesof S that can be matched in a matching of G. Our first result is a newrandomized algorithm for the Maximum Subset Matching problem thatimproves upon the fastest known algorithms for this problem. Our algorithmruns in Õ(ms(ω-1)/2) time if m ≥ s(ω+1)/2) and in Õ(sω) time ifm ≤ s(ω+1)/2), where ω mis the number of edges from S to V \ S, and s = |S|. The algorithm isbased, in part, on a method for computing the rank of sparse rectangularinteger matrices. Our second result is a new algorithm for the All-Pairs Shortest Paths(APSP) problem. Given an undirected graph with n vertices, and withinteger weights from {1,..., W } assigned to its edges, we present analgorithm that solves the APSP problem in Õ(Wnω(1,1,µ)) time wherenµ = υc(G) is the vertex cover number of G and ω(1, 1, µ) is the timeneeded to compute the Boolean product of an n×n matrix with an n×nµmatrix. Already for the unweighted case this improves upon the previousO(n2+µ) and Õ(nω) time algorithms for this problem. In particular, if agraph has a vertex cover of size O(n0.29) then APSP in unweighted graphscan be solved in asymptotically optimal Õ(n2) time, and otherwise it canbe solved in O(n1.844υc(G)0.533) time. The common feature of both results is their use of algorithms developedin recent years for fast (sparse) rectangular matrix multiplication.

Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover