Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs

DOI10.1007/S11590-016-1007-7MaRDI QIDQ331973zbMATHOpenAlexFDO

Authors Zhao Zhang, Joong-Lyul Lee, Weili Wu, Du Ding-Zhu

Publication date 27 October 2016

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-016-1007-7

zbMATH Keywords

approximation algorithmdominating and absorbing setguaranteed performanceheterogeneous sensor networksstrongly connectedvirtual backbone

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
• A PTAS for weak minimum routing cost connected dominating set of unit disk graph
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
• Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
• A greedy approximation for minimum connected dominating sets
• Approximation algorithms for minimum-cost \(k\)-\((S,T)\) connected digraphs

Cites work

• scientific article; zbMATH DE number 5764849 (Why is no real title available?)
• A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs
• A PTAS for weak minimum routing cost connected dominating set of unit disk graph
• A greedy algorithm for the fault-tolerant connected dominating set in a general graph
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem
• An exact algorithm for minimum CDS with shortest path constraint in wireless networks
• An inequality in the geometry of numbers
• Approximation algorithms for connected dominating sets
• Efficient distributed algorithms for topology control problem with shortest path constraints
• Wireless networking, dominating and packing
• Über die Einlagerung von Kreisen in einen konvexen Bereich

Cited in

(3)

• A distributed approximation algorithm for strongly connected dominating-absorbent sets in asymmetric wireless ad-hoc networks
• Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks
• On constructing strongly connected dominating and absorbing set in 3-dimensional wireless ad hoc networks

This page was built for publication: Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs

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