









Abstract:In this paper, we study the problem of \emph{triangle counting} in an arbitrary anonymous graph $G$ with $n$ nodes and $m$ edges using the \emph{mobile-agent model}. Our triangle-counting method serves as a building block for solving related problems such as truss decomposition, triangle centrality, and local clustering coefficient computation. The agents operate synchronously, have distinct identifiers and limited memory, and communicate only when co-located. Starting from an arbitrary placement of $n$ agents, we first obtain a dispersed configuration, elect a leader, construct a spanning tree, and determine the maximum degree $\Delta$ and maximum agent identifier $\lambda$. A BFS tree is constructed separately, which is needed for repeated global communication. Using this setup, the agents enumerate triangles and compute node- and edge-level triangle information, which is subsequently used for truss and centrality computations. We also complement the theoretical analysis with simulation-based evaluations on representative graph instances. Overall, our results establish a mobile-agent-based framework for these fundamental graph analytics problems in anonymous networks.
From: Prabhat Kumar Chand [view email]
[v1]
Tue, 6 Feb 2024 03:00:12 UTC (390 KB)
[v2]
Tue, 24 Jun 2025 09:10:59 UTC (39 KB)
[v3]
Sat, 12 Sep 2026 01:59:13 UTC (387 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。