SplitPath: High throughput using multipath routing in dual-radio Wireless Sensor Networks

Article Computer Science, Theory & Methods

NEW HARDNESS RESULTS FOR ROUTING ON DISJOINT PATHS

Julia Chuzhoy et al.

Summary: The classical node-disjoint paths (NDP) problem aims to route the largest possible number of demand pairs via node-disjoint paths in an undirected graph. The current best approximation for this problem is rooted in a greedy algorithm with O(root n) approximation factor. The study of this problem extends to special cases like grid graphs or general planar graphs, where current approximation ratios are (O) over tilde (n(1/4)) and (O) over tilde (n(9/19)) respectively. The authors of this paper prove that NDP is 2(Omega(root log n))-hard to approximate, even in a planar graph with maximum vertex degree 3 and specific placement of source vertices. Furthermore, the same hardness of approximation ratio is shown for the closely related edge-disjoint paths (EDP) problem in subcubic planar graphs.

SIAM JOURNAL ON COMPUTING (2022)

Add to Collection

Article Computer Science, Information Systems

On Self-Configuring IoT With Dual Radios: A Cross-Layer Approach

Jinhwan Jung et al.

Summary: This paper proposes a joint self-configuring MAC and routing protocol called SEDA-Net, which can adaptively choose the best communication coordination and data delivery configuration based on different topologies and external conditions. Through extensive simulations and experiments, it is demonstrated that SEDA-Net can improve energy efficiency by up to 2.1 times compared to existing approaches.

IEEE TRANSACTIONS ON MOBILE COMPUTING (2022)

Add to Collection

Article Computer Science, Hardware & Architecture

On undirected two-commodity integral flow, disjoint paths and strict terminal connection problems

Alexsander A. de Melo et al.

Summary: The text discusses the NP-completeness of the simple two-commodity integral flow problem in directed and undirected cases. Various proofs and investigations have been conducted to explore the complexity of the problem under different demand scenarios, ultimately providing insights into the problem's complexity.

NETWORKS (2021)

Add to Collection

Article Computer Science, Information Systems