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.

翻译：图的3-可容许性是一种有前景的度量指标，可用于识别具有算法友好结构的现实世界网络。我们设计了一种算法，该算法能够在时间O(p^3 * m)和空间O(p^3 * n)内判定输入图G的3-可容许性是否至多为p，其中m为G的边数，n为顶点数。据我们所知，这是首个明确计算3-可容许性的算法。该算法在时间和空间复杂度上对输入规模的线性依赖，结合其本身‘乐观’的设计理念，使其具备实际可行性。我们通过对corpussize个现实世界网络语料库的实验评估验证了这一点。实验结果出人意料地表明，尽管3-可容许性比2-可容许性具有更优的算法特性，但大多数现实世界网络的3-可容许性并未比2-可容许性大很多。