View in EDS

On the Broadcast problem for mobile agents in dynamic networks.

Saved in:
Bibliographic Details
Title: On the Broadcast problem for mobile agents in dynamic networks.
Authors: Das, Shantanu1 (AUTHOR), Giachoudis, Nikos2 (AUTHOR), Luccio, Flaminia L.3 (AUTHOR), Markou, Euripides1,4 (AUTHOR) emarkou@uoi.gr
Source: Discrete Applied Mathematics. Jan2026, Vol. 379, p194-208. 15p.
Subjects: Mobile agent systems, Computer networks, Telecommunication systems, Information dissemination, Algorithms, Topology, Applied sciences
Abstract: We study the standard communication problem of broadcast for mobile agents moving in a network, where a single agent called source, has to transmit a vital information to all other agents in the network. The agents move autonomously in the network and can communicate with other agents only when they meet at a node. Previous studies of this problem were restricted to static networks while, in this paper, we consider the problem in dynamic networks modeled as an evolving graph. The dynamicity of the graph is unknown to the agents; in each round an adversary selects which edges of the graph are available, and an agent can choose to traverse one of the available edges adjacent to its current location. The only restriction on the adversary is that the subgraph of available edges in each round must span all nodes; in other words the evolving graph is constantly connected. The agents have global visibility allowing them to see the location of all agents in the graph and move accordingly. Depending on the topology of the underlying graph, we determine the minimum value of k > 0 , such that the broadcast from a source agent to k other agents can be solved in dynamic networks. While k = 2 agents are sufficient for ring networks, much larger teams of agents are necessary for denser graphs such as grid graphs and hypercubes, and finally for complete graphs of n nodes k ≥ n − 2 agents are necessary and sufficient. We show lower bounds on the number of agents and provide algorithms for solving broadcast using the minimum number of agents, for various topologies. These results show how the connectivity of the underlying graph affects the communication capability of a team of mobile agents in constantly connected dynamic networks. [ABSTRACT FROM AUTHOR]
Copyright of Discrete Applied Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 189759837
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: On the Broadcast problem for mobile agents in dynamic networks.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Das%2C+Shantanu%22">Das, Shantanu</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Giachoudis%2C+Nikos%22">Giachoudis, Nikos</searchLink><relatesTo>2</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Luccio%2C+Flaminia+L%2E%22">Luccio, Flaminia L.</searchLink><relatesTo>3</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Markou%2C+Euripides%22">Markou, Euripides</searchLink><relatesTo>1,4</relatesTo> (AUTHOR)<i> emarkou@uoi.gr</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Discrete+Applied+Mathematics%22">Discrete Applied Mathematics</searchLink>. Jan2026, Vol. 379, p194-208. 15p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Mobile+agent+systems%22">Mobile agent systems</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+networks%22">Computer networks</searchLink><br /><searchLink fieldCode="DE" term="%22Telecommunication+systems%22">Telecommunication systems</searchLink><br /><searchLink fieldCode="DE" term="%22Information+dissemination%22">Information dissemination</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Topology%22">Topology</searchLink><br /><searchLink fieldCode="DE" term="%22Applied+sciences%22">Applied sciences</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: We study the standard communication problem of broadcast for mobile agents moving in a network, where a single agent called source, has to transmit a vital information to all other agents in the network. The agents move autonomously in the network and can communicate with other agents only when they meet at a node. Previous studies of this problem were restricted to static networks while, in this paper, we consider the problem in dynamic networks modeled as an evolving graph. The dynamicity of the graph is unknown to the agents; in each round an adversary selects which edges of the graph are available, and an agent can choose to traverse one of the available edges adjacent to its current location. The only restriction on the adversary is that the subgraph of available edges in each round must span all nodes; in other words the evolving graph is constantly connected. The agents have global visibility allowing them to see the location of all agents in the graph and move accordingly. Depending on the topology of the underlying graph, we determine the minimum value of k > 0 , such that the broadcast from a source agent to k other agents can be solved in dynamic networks. While k = 2 agents are sufficient for ring networks, much larger teams of agents are necessary for denser graphs such as grid graphs and hypercubes, and finally for complete graphs of n nodes k ≥ n − 2 agents are necessary and sufficient. We show lower bounds on the number of agents and provide algorithms for solving broadcast using the minimum number of agents, for various topologies. These results show how the connectivity of the underlying graph affects the communication capability of a team of mobile agents in constantly connected dynamic networks. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Discrete Applied Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=189759837
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.dam.2025.08.031
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 15
        StartPage: 194
    Subjects:
      – SubjectFull: Mobile agent systems
        Type: general
      – SubjectFull: Computer networks
        Type: general
      – SubjectFull: Telecommunication systems
        Type: general
      – SubjectFull: Information dissemination
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Topology
        Type: general
      – SubjectFull: Applied sciences
        Type: general
    Titles:
      – TitleFull: On the Broadcast problem for mobile agents in dynamic networks.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Das, Shantanu
      – PersonEntity:
          Name:
            NameFull: Giachoudis, Nikos
      – PersonEntity:
          Name:
            NameFull: Luccio, Flaminia L.
      – PersonEntity:
          Name:
            NameFull: Markou, Euripides
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 30
              M: 01
              Text: Jan2026
              Type: published
              Y: 2026
          Identifiers:
            – Type: issn-print
              Value: 0166218X
          Numbering:
            – Type: volume
              Value: 379
          Titles:
            – TitleFull: Discrete Applied Mathematics
              Type: main
ResultId 1