Dual power assignment via second Hamiltonian cycle

DOI10.1016/J.JCSS.2017.10.002MaRDI QIDQ1686228zbMATH OpenOpenAlexFDO

Authors A. Karim Abu-Affash, Paz Carmi, Anat Parush Tzur

Publication date 21 December 2017

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmcomputational geometrypower assignment

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Abstract: A power assignment is an assignment of transmission power to each of the wireless nodes of a wireless network, so that the induced graph satisfies some desired properties. The cost of a power assignment is the sum of the assigned powers. In this paper, we consider the dual power assignment problem, in which each wireless node is assigned a high- or low-power level, so that the induced graph is strongly connected and the cost of the assignment is minimized. We improve the best known approximation ratio from $fracp{i}^{2}6-frac136+epsilonhickapprox1.617$ to $frac117hickapprox1.571$. Moreover, we show that the algorithm of Khuller et al. for the strongly connected spanning subgraph problem, which achieves an approximation ratio of $1.61$, is $1.522$-approximation algorithm for symmetric directed graphs. The innovation of this paper is in achieving these results via utilizing interesting properties for the existence of a second Hamiltonian cycle.

Recommendations

• On dual power assignment optimization for biconnectivity
• scientific article; zbMATH DE number 147635
• Two edge-disjoint Hamiltonian cycles of powers of a graph
• A note on the 2-power of Hamilton cycles
• scientific article; zbMATH DE number 7559398
• A doubly cyclic channel assignment problem
• On the General Class of Two-Sided Power Distribution
• Powers of Hamiltonian cycles in multipartite graphs
• Two Hamiltonian cycles
• Algorithm Theory - SWAT 2004

Cites work

• scientific article; zbMATH DE number 1500550 (Why is no real title available?)
• Approximating Transitive Reductions for Directed Networks
• Approximating the Minimum Equivalent Digraph
• Approximating the minimum strongly connected subgraph via a matching lower bound
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• Independent dominating sets and a second hamiltonian cycle in regular graphs
• Independent dominating sets and hamiltonian cycles
• Min-power strong connectivity
• On Hamiltonian Circuits
• On strongly connected digraphs with bounded cycle length
• Power assignment in radio networks with two power levels
• Power consumption in packet radio networks
• Uniqueness of maximal dominating cycles in 3‐regular graphs and of hamiltonian cycles in 4‐regular graphs
• Wireless network design via 3-decompositions

Cited in

(1)

• Approximation algorithm for receiver interference problem in dual power wireless sensor networks

This page was built for publication: Dual power assignment via second Hamiltonian cycle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1686228)