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

DOI10.1007/s11590-016-1007-7zbMath1355.90103OpenAlexW2290747859MaRDI QIDQ331973

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

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)

Related Items (1)

On constructing strongly connected dominating and absorbing set in 3-dimensional wireless ad hoc networks

Cites Work

• Unnamed Item
• A greedy algorithm for the fault-tolerant connected dominating set in a general graph
• Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem
• An exact algorithm for minimum CDS with shortest path constraint in wireless networks
• Über die Einlagerung von Kreisen in einen konvexen Bereich
• An inequality in the geometry of numbers
• Approximation algorithms for connected dominating sets
• A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs
• Wireless networking, dominating and packing
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• EFFICIENT DISTRIBUTED ALGORITHMS FOR TOPOLOGY CONTROL PROBLEM WITH SHORTEST PATH CONSTRAINTS
• A PTAS for Weak Minimum Routing Cost Connected Dominating Set of Unit Disk Graph

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