Partial gathering of mobile agents in dynamic tori.
Saved in:
| Title: | Partial gathering of mobile agents in dynamic tori. |
|---|---|
| Authors: | Shibata, Masahiro1 (AUTHOR), Kitamura, Naoki2 (AUTHOR), Eguchi, Ryota3 (AUTHOR), Sudo, Yuichi4 (AUTHOR), Nakamura, Junya5 (AUTHOR), Kim, Yonghwan6 (AUTHOR) |
| Source: | Computer Journal. Oct2025, Vol. 68 Issue 10, p1485-1501. 17p. |
| Subjects: | Mobile agent systems, Computational complexity |
| Abstract: | In this paper, we consider the partial gathering problem of mobile agents in dynamic tori. This problem requires |$k$| agents distributed in the network to reach a configuration such that either at least |$g$| agents or no agent exists at each node. Thus far, in dynamic graphs, partial gathering is considered in 1-interval connected rings, where one of the links in the ring may be missing at each time step. In this paper, we consider another dynamic topology. Concretely, we consider partial gathering in |$n\times n$| dynamic tori such that each of the row and column rings is represented as a 1-interval connected ring. In such networks, when |$k = O(gn)$| , focusing on the relationship between the values of |$k, n$| , and |$g$| , we characterize the solvability of the problem and analyze the move complexity. First, we show that agents cannot solve the problem when |$k = o(gn)$|. Second, we show that agents can achieve partial gathering with a total number of |$O(gn^{3})$| moves when |$2gn+2n-1\le k \le 2gn + 6n +16g -12$|. Finally, we show that agents can achieve partial gathering with a total number of |$\Theta (gn^{2})$| moves when |$k\ge 2gn + 6n +16g -11$|. [ABSTRACT FROM AUTHOR] |
| Copyright of Computer Journal is the property of Oxford University Press / USA 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: 188809779 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Partial gathering of mobile agents in dynamic tori. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Shibata%2C+Masahiro%22">Shibata, Masahiro</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Kitamura%2C+Naoki%22">Kitamura, Naoki</searchLink><relatesTo>2</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Eguchi%2C+Ryota%22">Eguchi, Ryota</searchLink><relatesTo>3</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Sudo%2C+Yuichi%22">Sudo, Yuichi</searchLink><relatesTo>4</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Nakamura%2C+Junya%22">Nakamura, Junya</searchLink><relatesTo>5</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Kim%2C+Yonghwan%22">Kim, Yonghwan</searchLink><relatesTo>6</relatesTo> (AUTHOR) – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Computer+Journal%22">Computer Journal</searchLink>. Oct2025, Vol. 68 Issue 10, p1485-1501. 17p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Mobile+agent+systems%22">Mobile agent systems</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: In this paper, we consider the partial gathering problem of mobile agents in dynamic tori. This problem requires |$k$| agents distributed in the network to reach a configuration such that either at least |$g$| agents or no agent exists at each node. Thus far, in dynamic graphs, partial gathering is considered in 1-interval connected rings, where one of the links in the ring may be missing at each time step. In this paper, we consider another dynamic topology. Concretely, we consider partial gathering in |$n\times n$| dynamic tori such that each of the row and column rings is represented as a 1-interval connected ring. In such networks, when |$k = O(gn)$| , focusing on the relationship between the values of |$k, n$| , and |$g$| , we characterize the solvability of the problem and analyze the move complexity. First, we show that agents cannot solve the problem when |$k = o(gn)$|. Second, we show that agents can achieve partial gathering with a total number of |$O(gn^{3})$| moves when |$2gn+2n-1\le k \le 2gn + 6n +16g -12$|. Finally, we show that agents can achieve partial gathering with a total number of |$\Theta (gn^{2})$| moves when |$k\ge 2gn + 6n +16g -11$|. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Computer Journal is the property of Oxford University Press / USA 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=188809779 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1093/comjnl/bxaf052 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 17 StartPage: 1485 Subjects: – SubjectFull: Mobile agent systems Type: general – SubjectFull: Computational complexity Type: general Titles: – TitleFull: Partial gathering of mobile agents in dynamic tori. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Shibata, Masahiro – PersonEntity: Name: NameFull: Kitamura, Naoki – PersonEntity: Name: NameFull: Eguchi, Ryota – PersonEntity: Name: NameFull: Sudo, Yuichi – PersonEntity: Name: NameFull: Nakamura, Junya – PersonEntity: Name: NameFull: Kim, Yonghwan IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 10 Text: Oct2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 00104620 Numbering: – Type: volume Value: 68 – Type: issue Value: 10 Titles: – TitleFull: Computer Journal Type: main |
| ResultId | 1 |
