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

DOI10.1007/978-3-031-32733-9_12arXiv1805.04071OpenAlexW4377971759MaRDI QIDQ6148068

Yi-Jun Chang

Publication date: 11 January 2024

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1805.04071

zbMATH Keywords

diameterradio networksenergy-aware computation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed minimum dominating set approximations in restricted families of graphs
• Quasi-optimal energy-efficient leader election algorithms in radio networks
• Energy efficient randomised communication in unknown AdHoc networks
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• Power consumption in packet radio networks
• A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
• Energy-Efficient Initialization Protocols for Ad-hoc Radio Networks
• Energy and Time Efficient Broadcasting in Known Topology Radio Networks
• Fast Distributed Approximations in Planar Graphs
• On Broadcasting in Radio Networks--Problem Analysis and Protocol Design
• Weak communication in single‐hop radio networks: adjusting algorithms to industrial standards
• Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
• Exponential separations in the energy complexity of leader election
• Efficient algorithms for leader election in radio networks
• The Energy Complexity of Broadcast
• Minor Excluded Network Families Admit Fast Distributed Algorithms
• Planar diameter via metric compression
• Contention resolution with log-logstar channel accesses
• A Local Constant Factor MDS Approximation for Bounded Genus Graphs
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Automata, Languages and Programming
• Sleeping is Efficient: MIS in O (1)-rounds Node-averaged Awake Complexity
• The Energy Complexity of BFS in Radio Networks
• Algorithms - ESA 2003
• Algorithms and Computation
• Near-Optimal Time–Energy Tradeoffs for Deterministic Leader Election

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