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

DOI10.1007/S11590-016-1007-7zbMATH Open1355.90103OpenAlexW2290747859MaRDI QIDQ331973FDOQ331973

Du Ding-Zhu, 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

Recommendations

• On the approximability and hardness of the minimum connected dominating set with routing cost constraint
• On the approximability and hardness of the minimum connected dominating set with routing cost constraint
• 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

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)

Cites Work

• A greedy algorithm for the fault-tolerant connected dominating set in a general graph
• Wireless networking, dominating and packing
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• An exact algorithm for minimum CDS with shortest path constraint in wireless networks
• Approximation algorithms for connected dominating sets
• Title not available (Why is that?)
• A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs
• Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem
• 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
• Über die Einlagerung von Kreisen in einen konvexen Bereich
• An inequality in the geometry of numbers

Cited In (1)

• 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)