2018/05/10 by Yi‐Jun Chang, Chang, Yi-Jun · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1805.04071
openalex publication_date 2018/05/10 · openalex created_date 2018/05/17 · openalex updated_date 2026/07/28
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 maximum 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-efficient algorithms that consume only poly log n energy. However, there exist some problems, such as computing the diameter of the graph, that require Ω(n) energy to solve. To improve energy efficiency for these problems, we focus on a special graph class: bounded-genus graphs. We present algorithms for computing the exact diameter, the exact global minimum cut size, and a (1 ±ε)-approximate s-t minimum cut size with O(√(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.