EUVIMEDEUVIMED entdecken
Crossref

Performance Bound Analysis of Linear Consensus Algorithm on Strongly Connected Graphs Using Effective Resistance and Reversiblization

Takumi Yonaiyama, Kazuhiro Sato

SIAM Journal on Matrix Analysis and Applications · 30.06.2026 · 47 (2) · 852-875

DOI: 10.1137/25m1737638 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Matrix Analysis and Applications, online erschienen am 19.06.2026. Verfasst von Takumi Yonaiyama und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 31 Literaturangaben. Gefördert von: Japan Society for the Promotion of Science.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the performance of the linear consensus algorithm on strongly connected directed graphs using the linear quadratic (LQ) cost as a performance measure. In particular, we derive bounds on the LQ cost by leveraging effective resistance and reversiblization. Our results extend previous analyses—which were limited to reversible cases—to the nonreversible setting. To facilitate this generalization, we introduce novel concepts, termed the back-and-forth path and the pivot node, which serve as effective alternatives to traditional techniques that require reversibility. Moreover, we apply our approach to Cayley graphs and random geometric graphs to estimate the LQ cost without the reversibility assumption. The proposed approach provides a framework that can be adapted to other contexts where reversibility is typically assumed.

Förderung

  • Japan Society for the Promotion of Science

Zitieren

APA

Yonaiyama, T., & Sato, K. (2026). Performance Bound Analysis of Linear Consensus Algorithm on Strongly Connected Graphs Using Effective Resistance and Reversiblization. SIAM Journal on Matrix Analysis and Applications, 47(2), 852-875. https://doi.org/10.1137/25m1737638

Vancouver

Yonaiyama T, Sato K. Performance Bound Analysis of Linear Consensus Algorithm on Strongly Connected Graphs Using Effective Resistance and Reversiblization. SIAM Journal on Matrix Analysis and Applications. 2026;47(2):852-875. doi:10.1137/25m1737638

BibTeX
@article{Yonaiyama2026,
  author = {Yonaiyama, Takumi and Sato, Kazuhiro},
  title = {Performance Bound Analysis of Linear Consensus Algorithm on Strongly Connected Graphs Using Effective Resistance and Reversiblization},
  journal = {SIAM Journal on Matrix Analysis and Applications},
  year = {2026},
  volume = {47},
  number = {2},
  pages = {852--875},
  doi = {10.1137/25m1737638}
}
Kostenlos starten →