ABSTRACT Reducing the running time of graph algorithms is vital for tackling real‐world problems such as shortest paths and matching in large‐scale graphs, where path information plays a crucial role. To address this critical challenge, this paper introduces a graph restructuring algorithm that identifies bipartite cliques and replaces them with tripartite graphs. This restructuring leads to fewer edges while preserving complete graph path information, enabling the direct application of algorithms like matching and all‐pairs shortest paths to achieve significant runtime reductions, especially for large, dense graphs. The running time of the proposed algorithm for a graph , with and is , which is better than , the running time of the best existing algorithm for speeding‐up other graph algorithms (the Feder–Motwani ( FM ) algorithm), where . Both the FM algorithm and the proposed algorithm are originally formulated for bipartite graphs, but can also be applied to general directed or undirected graphs. Our extensive experimental analysis demonstrates that the proposed algorithm achieves up to 21.26% higher reduction in the number of edges and runs up to faster than the FM algorithm. On large synthetic graphs with up to 1.05 billion edges, it attains a reduction in the number of edges of up to 74.36%. On real‐world graphs, it achieves a reduction in the number of edges by up to 46.8%. Furthermore, when used as a preprocessing step, our approach yields up to a speedup for the matching algorithms on large synthetic graphs, and up to a speedup for the All‐Pairs Shortest Path algorithms on real‐world graphs, when compared to using the given graph as input.

Energy harvesting sources, such as solar, wind, or vibration, combined with rechargeable batteries, are a promising way to power Low-Power Wide-Area Network (LPWAN) devices to reduce the cost and frequency of redeploying single-use batteries. However, being oblivious to the usage of rechargeable batteries can severely reduce their capacity to store energy, which is also known as the battery lifespan. Existing energy-aware protocols mostly focus on network lifetime and pay little attention to maximizing the battery lifespan of network nodes while the latter can directly help reduce battery waste and enhance environmental sustainability. In this paper, we propose the first Media Access Control (MAC) protocol to maximize the minimum battery lifespan among all nodes in an LPWAN based on LoRa. Our approach differs from traditional objectives focusing on min-imizing energy consumption or maximizing network lifetime as they may not necessarily maximize battery lifespan. The proposed MAC protocol leverages the concept of software-defined batteries to regulate the energy stored and consumed by each node's battery based on estimated energy requirements, green energy generation, and changes in data utility. To limit the degradation of battery capacity due to continuous charging/discharging, the underpinning idea is to determine an appropriate time for each transmission considering its impact on battery degradation while also minimizing the impact on data utility. Furthermore, the energy stored in each battery is limited to reduce calendar aging, the natural degradation of battery capacity over time. The proposed protocol is local, online, and asynchronous, and incurs low overhead. We evaluate our approach through experiments on a LoRa network and large-scale simulations in NS-3. The experiments show that the proposed MAC protocol improves battery lifespan by up to 69.7% and data utility by up to 39% in a current LoRa network while incurring a CPU utilization overhead of only 12 % at each LoRa node.

Autonomous mobile robots (AMRs) are capable of carrying out operations continuously for 24/7, which enables them to optimize tasks, increase throughput, and meet demanding operational requirements. To ensure seamless and uninterrupted operations, an effective coordination of task allocation and charging schedules is crucial while considering the preservation of battery sustainability. Moreover, regular preventive maintenance plays an important role in enhancing the robustness of AMRs against hardware failures and abnormalities during task execution. However, existing works do not consider the influence of properly scheduling AMR maintenance on both task downtime and battery lifespan. In this paper, we proposeMTC,a maintenance-aware task and chargingscheduler designed for fleets of AMR operating continuously in highly automated environments.MTCleverages Linear Programming (LP) to first help decide the best time to schedule maintenance for a given set of AMRs. Subsequently, the Kuhn-Munkres algorithm, a variant of the Hungarian algorithm, is used to finalize task assignments and carry out the charge scheduling to minimize the combined cost of task downtime and battery degradation. Experimental results demonstrate the effectiveness ofMTC, reducing the combined total cost up to 3.45 times and providing up to 68% improvement in battery capacity degradation compared to the baselines.