A practical algorithm for 3-admissibility
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914175834390528 |
|---|---|
| author | Awofeso, Christine Greaves, Patrick Lachish, Oded Reidl, Felix |
| author_facet | Awofeso, Christine Greaves, Patrick Lachish, Oded Reidl, Felix |
| contents | The $3$-admissibility of a graph is a promising measure to identify real-world networks that have an algorithmically favourable structure.
We design an algorithm that decides whether the $3$-admissibility of an input graph~$G$ is at most~$p$ in time~\runtime and space~\memory, where $m$ is the number of edges in $G$ and $n$ the number of vertices. To the best of our knowledge, this is the first explicit algorithm to compute the $3$-admissibility.
The linear dependence on the input size in both time and space complexity, coupled with an `optimistic' design philosophy for the algorithm itself, makes this algorithm practicable, as we demonstrate with an experimental evaluation on a corpus of \corpussize real-world networks.
Our experimental results show, surprisingly, that the $3$-admissibility of most real-world networks is not much larger than the $2$-admissibility, despite the fact that the former has better algorithmic properties than the latter. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_01121 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A practical algorithm for 3-admissibility Awofeso, Christine Greaves, Patrick Lachish, Oded Reidl, Felix Data Structures and Algorithms The $3$-admissibility of a graph is a promising measure to identify real-world networks that have an algorithmically favourable structure. We design an algorithm that decides whether the $3$-admissibility of an input graph~$G$ is at most~$p$ in time~\runtime and space~\memory, where $m$ is the number of edges in $G$ and $n$ the number of vertices. To the best of our knowledge, this is the first explicit algorithm to compute the $3$-admissibility. The linear dependence on the input size in both time and space complexity, coupled with an `optimistic' design philosophy for the algorithm itself, makes this algorithm practicable, as we demonstrate with an experimental evaluation on a corpus of \corpussize real-world networks. Our experimental results show, surprisingly, that the $3$-admissibility of most real-world networks is not much larger than the $2$-admissibility, despite the fact that the former has better algorithmic properties than the latter. |
| title | A practical algorithm for 3-admissibility |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.01121 |