PTAS for minimum connected dominating set with routing cost constraint in wireless sensor networks

DOI10.1007/978-3-642-17458-2_21MaRDI QIDQ3066162zbMATH OpenOpenAlexFDO

Authors Qiang Ye, Jioafei Zhong, Yuexuan Wang, Haesun Park, Hongwei Du, Wonjun Lee

Publication date 8 January 2011

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-17458-2_21

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Recommendations

• Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks
• PTAS for routing-cost constrained minimum connected dominating set in growth bounded graphs
• A PTAS for weak minimum routing cost connected dominating set of unit disk graph
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks

Cited in

(9)

• A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
• A PTAS for minimum d-hop connected dominating set in growth-bounded graphs
• PTAS for routing-cost constrained minimum connected dominating set in growth bounded graphs
• A BETTER APPROXIMATION FOR MINIMUM AVERAGE ROUTING PATH CLUSTERING PROBLEM IN 2-D UNDERWATER SENSOR NETWORKS
• Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks
• A PTAS for weak minimum routing cost connected dominating set of unit disk graph
• An exact algorithm for minimum CDS with shortest path constraint in wireless networks
• The wake up dominating set problem
• A simpler PTAS for connected k-path vertex cover in homogeneous wireless sensor network

This page was built for publication: PTAS for minimum connected dominating set with routing cost constraint in wireless sensor networks

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