Improved Linear-Time Construction of Minimal Dominating Set via Mobile Agents

2025-11-25 · Prabhat Kumar Chand, Anisur Rahaman Molla arxiv

Mobile agents have emerged as a powerful framework for solving fundamental graph problems in distributed settings in recent times. These agents, modelled as autonomous physical or software entities, possess local computation power, finite memory and have the ability to traverse a graph, offering efficient solutions to a range of classical problems. In this work, we focus on the problem of computing a \emph{minimal dominating set} (mDS) in anonymous graphs using mobile agents. Building on the recently proposed optimal dispersion algorithm on the synchronous mobile agent model, we design two new algorithms that achieve a \emph{linear-time} solution for this problem in the synchronous setting. Specifically, given a connected $n$-node graph with $n$ agents initially placed in either rooted or arbitrary configurations, we show that an mDS can be computed in $O(n)$ rounds using only $O(\log n)$ bits of memory per agent, without using any prior knowledge of any global parameters. This improves upon the best-known complexity results in the literature over the same model. In addition, as natural by-products of our methodology, our algorithms also construct a spanning tree and elect a unique leader in $O(n)$ rounds, which are also important results of independent interest in the mobile-agent framework.

📄 PDF Abstract BibTeX arXiv:2511.19880

Code (0)

등록된 구현이 없습니다.

Trees and Graphs with Non Log-concave Dominating Set Sequence via AI Tools

2026-05-04 · Alina Du, Steven Heilman, Greta Panova arxiv

We give new examples of graphs and trees with dominating set sequences that are not log-concave. These examples were generated by PatternBoost, a transformer-based reinforcement learning software developed by Charton-Ell…

Reinforcement Learning

Classification Using Proximity Catch Digraphs (Technical Report)

2017-05-22 · Artür Manukyan, Elvan Ceyhan

We employ random geometric digraphs to construct semi-parametric classifiers. These data-random digraphs are from parametrized random digraph families called proximity catch digraphs (PCDs). A related geometric digraph f…

Classification General Classification

Statistical Non-linear Reconstruction Loss for Image Anomaly Detection

2026-07-14 · Nguyen Minh Tri, Hoang Khuong Duy, Huynh Cong Viet Ngu arxiv

Reconstruction-based methods are a cornerstone of unsupervised image anomaly detection, but they remain vulnerable to \emph{outlier leakage}, where standard mean squared error (MSE) loss drives the model to faithfully re…

Anomaly Detection

FaCT-GS: Fast and Scalable CT Reconstruction with Gaussian Splatting

2026-04-02 · Pawel Tomasz Pieta, Rasmus Juul Pedersen, Sina Borgi, Jakob Sauer Jørgensen 외 arxiv

Gaussian Splatting (GS) has emerged as a dominating technique for image rendering and has quickly been adapted for the X-ray Computed Tomography (CT) reconstruction task. However, despite being on par or better than many…

BERT-based Financial Sentiment Index and LSTM-based Stock Return Predictability

2019-06-21 · Joshua Zoen Git Hiew, Xin Huang, Hao Mou, Duan Li 외

Traditional sentiment construction in finance relies heavily on the dictionary-based approach, with a few exceptions using simple machine learning techniques such as Naive Bayes classifier. While the current literature h…

Sentiment Analysis