Journal
THEORETICAL COMPUTER SCIENCE
Volume 982, Issue -, Pages -Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2023.114279
Keywords
Distributed graph algorithms
Categories
Ask authors/readers for more resources
This paper investigates the energy complexity of distributed graph problems in multi-hop radio networks. Recent studies have shown that some problems can be solved with energy-efficient algorithms, while others require significant energy consumption. To improve energy efficiency, this paper focuses on bounded-genus graphs and proposes corresponding algorithms.
This paper investigates the energy complexity of distributed graph problems in multi-hop radio networks, where the energy cost of an algorithm is measured by the maximu m number of awake rounds of a vertex. Recent works revealed that some problems, such as broadcast, breadth-first search, and maximal matching, can be solved with energy-ecient algorithms that consume only poly log n energy. However, there exist some problems, such as computing the diameter of the graph, that requir e Omega(n) energy to solve. To improve energ y eciency for these problems, we focus on a special graph class: bounded-genus graphs. We present algorithms for computin g the exact diameter, the exact global minimum cut size , and a (1 +/- epsilon)-approximate s-t minimum cut root size with O( root n) energy for bounded-genus graphs. Our approach is based on a generic framework that divides the vertex set into high-degree and low-degree parts and leverages the structural properties of bounded-genus graphs to control the number of certain connected components in the subgraph induced by the low-degree part.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available