A practical algorithm for 2-admissibility
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916724612268032 |
|---|---|
| author | Awofeso, Christine Greaves, Patrick Lachish, Oded Reidl, Felix |
| author_facet | Awofeso, Christine Greaves, Patrick Lachish, Oded Reidl, Felix |
| contents | The $2$-admissibility of a graph is a promising measure to identify real-world networks which have an algorithmically favourable structure. In contrast to other related measures, like the weak/strong $2$-colouring numbers or the maximum density of graphs that appear as $1$-subdivisions, the $2$-admissibility can be computed in polynomial time. However, so far these results are theoretical only and no practical implementation to compute the $2$-admissibility exists.
Here we present an algorithm which decides whether the $2$-admissibility of an input graph $G$ is at most $p$ in time $O(p^4 |V(G)|)$ and space $O(|E(G)| + p^2)$. The simple structure of the algorithm makes it easy to implement. We evaluate our implementation on a corpus of 214 real-world networks and find that the algorithm runs efficiently even on networks with millions of edges, that it has a low memory footprint, and that indeed many networks have a small $2$-admissibility. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_03419 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A practical algorithm for 2-admissibility Awofeso, Christine Greaves, Patrick Lachish, Oded Reidl, Felix Data Structures and Algorithms Combinatorics 05C85 F.2.2 The $2$-admissibility of a graph is a promising measure to identify real-world networks which have an algorithmically favourable structure. In contrast to other related measures, like the weak/strong $2$-colouring numbers or the maximum density of graphs that appear as $1$-subdivisions, the $2$-admissibility can be computed in polynomial time. However, so far these results are theoretical only and no practical implementation to compute the $2$-admissibility exists. Here we present an algorithm which decides whether the $2$-admissibility of an input graph $G$ is at most $p$ in time $O(p^4 |V(G)|)$ and space $O(|E(G)| + p^2)$. The simple structure of the algorithm makes it easy to implement. We evaluate our implementation on a corpus of 214 real-world networks and find that the algorithm runs efficiently even on networks with millions of edges, that it has a low memory footprint, and that indeed many networks have a small $2$-admissibility. |
| title | A practical algorithm for 2-admissibility |
| topic | Data Structures and Algorithms Combinatorics 05C85 F.2.2 |
| url | https://arxiv.org/abs/2505.03419 |