The energy complexity of diameter and minimum cut computation in bounded-genus networks

DOI10.1016/J.TCS.2023.114279MaRDI QIDQ6199403zbMATH OpenOpenAlexFDO

Authors Yi-Jun Chang

Publication date 23 February 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2023.114279

zbMATH Keywords

distributed graph algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A local constant factor MDS approximation for bounded genus graphs
• A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
• Adversary immune leader election in ad hoc radio networks
• Algorithms and Computation
• Automata, Languages and Programming
• Contention resolution with log-logstar channel accesses
• Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
• Distributed minimum dominating set approximations in restricted families of graphs
• Efficient algorithms for leader election in radio networks
• Energy and Time Efficient Broadcasting in Known Topology Radio Networks
• Energy efficient randomised communication in unknown AdHoc networks
• Exponential separations in the energy complexity of leader election
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Fast Distributed Approximations in Planar Graphs
• scientific article; zbMATH DE number 2080260 (Why is no real title available?)
• scientific article; zbMATH DE number 2089983 (Why is no real title available?)
• Local computation: lower and upper bounds
• Minor excluded network families admit fast distributed algorithms
• Near-Optimal Time–Energy Tradeoffs for Deterministic Leader Election
• On Broadcasting in Radio Networks--Problem Analysis and Protocol Design
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• Planar diameter via metric compression
• Power consumption in packet radio networks
• Quasi-optimal energy-efficient leader election algorithms in radio networks
• Sleeping is Efficient: MIS in O (1)-rounds Node-averaged Awake Complexity
• The Energy Complexity of BFS in Radio Networks
• The energy complexity of broadcast
• Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks
• Weak communication in single‐hop radio networks: adjusting algorithms to industrial standards

This page was built for publication: The energy complexity of diameter and minimum cut computation in bounded-genus networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199403)