2018/05/10 by Yi‐Jun Chang, Chang, Yi-Jun · 1 citation
Computer Science · Mathematics · #Algorithm #Arboricity #Binary logarithm #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Computation #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #Degree (music) #Discrete mathematics #Distributed #FOS: Computer and information sciences #Genus #Graph #Mathematics #Maximum cut #Mobile Ad Hoc Networks #Parallel #Physics #Planar graph #Vertex (graph theory) #Vertex cover #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1805.04071
published in arXiv (Cornell University) (Cornell University)
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.