A practical algorithm for 3 3 -admissibility

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

Read A practical algorithm for 3 3 -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-2512-01121.txt.

Description

Christine Awofeso, Patrick Greaves, Oded Lachish, and Felix Reidl design a practical algorithm for a graph measure in a 2025 paper. The 3-admissibility of a graph is a promising measure for spotting real-world networks with algorithmically favorable structure. Sparse, well-structured networks admit faster algorithms for many hard problems.

Their algorithm decides whether a graph's 3-admissibility is at most a given bound. They state its running time in terms of the number of edges and the bound, and its space in terms of vertices and the bound. A practical test lets analysts screen large real networks for the structure that makes them tractable.

Catalog record

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

Source: https://arxiv.org/abs/2512-01121

Browse the full library · About the Tower of Babel