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

Given a graph, a $k$-plex is a set of vertices in which each vertex is notadjacent to at most $k-1$ other vertices in the set. The maximum $k$-plexproblem, which asks for the largest $k$-plex from the given graph, is animportant but computationally challenging problem in applications such as graphmining and community detection. So far, there are many practical algorithms,but without providing theoretical explanations on their efficiency. We define anovel parameter of the input instance, $g_k(G)$, the gap between the degeneracybound and the size of the maximum $k$-plex in the given graph, and present anexact algorithm parameterized by this $g_k(G)$, which has a worst-case runningtime polynomial in the size of the input graph and exponential in $g_k(G)$. Inreal-world inputs, $g_k(G)$ is very small, usually bounded by $O(\log{(|V|)})$,indicating that the algorithm runs in polynomial time. We further extend ourdiscussion to an even smaller parameter $cg_k(G)$, the gap between thecommunity-degeneracy bound and the size of the maximum $k$-plex, and show thatwithout much modification, our algorithm can also be parameterized by$cg_k(G)$. To verify the empirical performance of these algorithms, we carryout extensive experiments to show that these algorithms are competitive withthe state-of-the-art algorithms. In particular, for large $k$ values such as$15$ and $20$, our algorithms dominate the existing algorithms. Finally,empirical analysis is performed to illustrate the effectiveness of theparameters and other key components in the implementation.

Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps