Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chand, Prabhat Kumar, Molla, Anisur Rahaman
Format:	Preprint
Published:	2025
Subjects:	Distributed, Parallel, and Cluster Computing Data Structures and Algorithms Multiagent Systems Robotics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Dispersion is (Almost) Optimal under (A)synchrony
by: Kshemkalyani, Ajay D., et al.
Published: (2025)

Agentic Distributed Computing
by: Kshemkalyani, Ajay D., et al.
Published: (2025)

Optimal Dispersion Under Asynchrony
by: Pattanayak, Debasish, et al.
Published: (2025)

Agent-based Leader Election, MST, and Beyond
by: Kshemkalyani, Ajay D., et al.
Published: (2024)

Computing Tree Structures in Anonymous Graphs via Mobile Agents
by: Chand, Prabhat Kumar, et al.
Published: (2025)

Distributed Butterfly Analysis using Mobile Agents
by: Chand, Prabhat Kumar, et al.
Published: (2025)

Agent-Based Triangle Counting: Unlocking Truss Decomposition, Triangle Centrality, and Local Clustering Coefficient
by: Chand, Prabhat Kumar, et al.
Published: (2024)

Location-Aware Dispersion on Anonymous Graphs
by: Himani, et al.
Published: (2026)

Asynchronous Collective Tree Exploration: a Distributed Algorithm, and a new Lower Bound
by: Cosson, Romain, et al.
Published: (2025)

Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs
by: Bonamy, Marthe, et al.
Published: (2025)

A Graph Isomorphism-based Decentralized Algorithm for Modular Robot Configuration Formation
by: Dutta, Ayan, et al.
Published: (2016)

All-to-All Communication with Mobile Edge Adversary: Almost Linearly More Faults, For Free
by: Fischer, Orr, et al.
Published: (2025)

Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
by: Ghaffari, Mohsen, et al.
Published: (2024)

Overlay Network Construction: Improved Overall and Node-Wise Message Complexity
by: Chang, Yi-Jun, et al.
Published: (2024)

Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs
by: Gil, Yuval
Published: (2024)

BinomialHash: A Constant Time, Minimal Memory Consistent Hash Algorithm
by: Coluzzi, Massimo, et al.
Published: (2024)

Distributed Download from an External Data Source in Faulty Majority Settings
by: Augustine, John, et al.
Published: (2024)

Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling
by: Dhulipala, Laxman, et al.
Published: (2024)

Honeybee: Byzantine Tolerant Decentralized Peer Sampling with Verifiable Random Walks
by: Zhang, Yunqi, et al.
Published: (2024)

Tight Bounds for Constant-Round Domination on Graphs of High Girth and Low Expansion
by: Lenzen, Christoph, et al.
Published: (2024)

Asynchronous Gathering of Opaque Robots with Mobility Faults
by: Pramanick, Subhajit, et al.
Published: (2025)

The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing
by: Weidner, Matthew, et al.
Published: (2023)

Parallel Algorithms for the One Sided Crossing Minimization Problem
by: Popa, Bogdan-Ioan, et al.
Published: (2025)

Eventually Lattice-Linear Algorithms
by: Gupta, Arya Tanmay, et al.
Published: (2023)

Massively Parallel Ruling Set Made Deterministic
by: Giliberti, Jeff, et al.
Published: (2024)

Parallel Batch-Dynamic Maximal Independent Set
by: Blelloch, Guy, et al.
Published: (2026)

An Implementation and Experimental Comparison of Dynamic Ordered Sets
by: Malek, Jordan
Published: (2024)

Constrained Cuts, Flows, and Lattice-Linearity
by: Streit, Robert, et al.
Published: (2025)

Distributed Reductions for the Maximum Weight Independent Set Problem
by: Borowitz, Jannick, et al.
Published: (2025)

Energy-Efficient Maximal Independent Sets in Radio Networks
by: Banasik, Dominick, et al.
Published: (2025)

Exploiting Multi-Core Parallelism in Blockchain Validation and Construction
by: Karmegam, Arivarasan, et al.
Published: (2026)

Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs
by: Baumecker, Malte, et al.
Published: (2025)

Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set
by: Ghaffari, Mohsen, et al.
Published: (2025)

MTASet: A Tree-based Set for Efficient Range Queries in Update-heavy Workloads
by: Manor, Daniel, et al.
Published: (2025)

A Nearly Linear-Time Distributed Algorithm for Maximum Cardinality Matching
by: Izumi, Taisuke, et al.
Published: (2023)

Improved Byzantine Agreement under an Adaptive Adversary
by: Dufoulon, Fabien, et al.
Published: (2025)

Improved All-Pairs Approximate Shortest Paths in Congested Clique
by: Bui, Hong Duc, et al.
Published: (2024)

Improved Massively Parallel Triangle Counting in $O(1)$ Rounds
by: Liu, Quanquan C., et al.
Published: (2024)

Improved Approximation Bounds for Minimum Weight Cycle in the CONGEST Model
by: Manoharan, Vignesh, et al.
Published: (2023)

Multi-Agent Online Graph Exploration on Cycles and Tadpole Graphs
by: Akker, Erik van den, et al.
Published: (2024)