A practical algorithm for 2 2 -admissibility

Christine Awofeso, Patrick Greaves, Oded Lachish, Felix Reidl · 2025

Read A practical algorithm for 2 2 -admissibility by Christine Awofeso, Patrick Greaves, Oded Lachish, Felix Reidl (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-03419.txt.

Description

Christine Awofeso and co-authors make a network measure practical at last. Their 2025 paper concerns 2-admissibility, a number that flags graphs with friendly structure for algorithms. Theory said it could be computed in polynomial time, yet no working tool existed. Their algorithm decides if the value stays under a chosen cap, with clean bounds on time and memory.

The design is simple enough to implement without fuss. They ran it on 214 real-world networks. It stayed fast even on graphs with millions of edges, and its memory use stayed low. Many real networks indeed carry small values, as hoped. The authors offer the tool to network scientists who sort and search huge graphs.

Catalog record

CREATORChristine Awofeso, Patrick Greaves, Oded Lachish, Felix Reidl
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE251 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-03419

Browse the full library · About the Tower of Babel