Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

7. Routing-Cost Constrained CDS

verfasst von : Ding-Zhu Du, Peng-Jun Wan

Erschienen in: Connected Dominating Set: Theory and Applications

Verlag: Springer New York

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Consider a graph as shown in Fig. 7.1. C = { 4, 5, 6} is a minimum CDS. G = (V, E). The minimum routing between nodes 1 and 3 not through C is 1-2-3 and through D is 1-4-5-6-2, which is significantly longer than 1-2-3. This example indicates a problem about CDS that while CDS is introduced to save resources in wireless networks, routing cost and communication delay may be increased.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Coverage
Nächstes Kapitel CDS in Disk-Containment Graphs
Literatur
1.
Akyildiz, I.F., Pompili, D., Melodia, T.: Underwater acoustic sensor networks: research challenges. Ad Hoc Network 3(3), 257–279 (2005)CrossRef
2.
Ambühl, C., Erlebach, T., Mihalák, M., Nunkesser, M.: Constant-approximation for minimum-weight (connected) dominating sets in unit disk graphs. Proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2006). Lecture Notes in Computer Science, vol. 4110 pp. 3–14. Springer, Berlin (2006)
3.
Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153–180 (1994)MATHCrossRef
4.
Baudis, G., Gröpl, C., Hougardy, S., Nierhoff, T., Prömel, H.J.: Approximating minimum spanning sets in hypergraphs and polymatroids. Technical Report, Humboldt-Universitt zu Berlin (2000)
5.
Benini, L., Castelli, G., Macii, A., Poncino, M., Scarsi, R.: A discrete-time battery model for high-level power estimation. Proceedings of DATE, pp. 35–39 (2000)
6.
Berman, P., Calinescu, G., Shah, C., Zelikovsky, A.: Power efficient monitoring management in sensor networks. IEEE Wireless Communication and Networking Conference (WCNC’04), Atlanta, pp. 2329–2334 (2004)
7.
Berman, P., Calinescu, G., Shah, C., Zelikovsky, A.: Efficient energy management in sensor networks. In: Xiao, Y., Pan, Y. (eds.) Ad Hoc and Sensor Networks, Wireless Networks and Mobile Computing, vol. 2. Nova Science Publishers, New York (2005)
8.
Bharghavan, V., Das, B.: Routing in ad hoc networks using minimum connected dominating sets. International Conference on Communication, Montreal, Canada (1997)
9.
Butenko, S., Kahruman-Anderoglu, S., Ursulenko, O.: On connected domination in unit ball graphs. Optim. Lett. 5(2), 195–205 (2011)MathSciNetMATHCrossRef
10.
Byrka, J., Grandoni, F., Rothvoss, T., Sanita, L.: An improved LP-based approximation for Steiner tree. STOC’10, pp. 583–592 (2010)
11.
Calinescu, G., Ellis, R.: On the lifetime of randomly deployed sensor networks. DialM-POMC the Fifth ACM SIGACTSIGOPS International Workshop on Foundation of Mobile Computing (2008)
12.
Calinescu, G., Kapoor, S., Olshevsky, A., Zelikovsky, A.: Network lifetime and power assignment in ad-hoc wireless networks. Proceedings of European Symposium on Algorithms (ESA’03), Lecture Notes in Computer Science, vol. 2832, pp. 114–126 (2003)MathSciNetCrossRef
13.
Cardei, M., Du, D.-Z.: Improving wireless sensor network lifetime through power aware organization. ACM Wireless Network. 11(3), 333–340 (2005)CrossRef
14.
Cardei, M., Cheng, M.X., Cheng, X., Du, D.-Z.: Connected domination in ad hoc wireless networks. In: Proceedings the Sixth International Conference on Computer Science and Informatics (CS&I’2002) (2002)
15.
Cardei, M., Thai, M., Li, Y., Wu, W.: Energy-efficient target coverage in wireless sensor networks. IEEE INFOCOM, pp. 1976–1984 (2005)
16.
Cardei, M., MacCallum, D., Cheng, X., Min, M., Jia, X., Li, D., Du, D.-Z.: Wireless sensor networks with energy efficient organization. J. Interconnect. Networks 3(3–4), 213–229 (2002)CrossRef
17.
Chen, Y.P., Liestman, A.L.: Approximating minimum size weakly-connected dominating sets for clustering mobile ad hoc networks. In: Proceedings of the Third ACM International Symposium on Mobile ad hoc Networking and Computing, Lausanne, Switzerland (2002)
18.
Cheng, M.X., Gong, X.: Maximum lifetime coverage preserving scheduling algorithms in sensor networks. J. Global Optim. 51(3), 447–462 (2011)MATHCrossRef
19.
Cheng, M.X., Ruan, L., Wu, W.: Achieving minimum coverage breach under bandwidth constraints in wireless sensor networks. INFOCOM, pp. 2638–2645 (2005)
20.
Cheng, M.X., Ruan, L., Wu, W.: Coverage breach problems in bandwidth-constrained sensor networks. TOSN 3(2), 12 (2007)CrossRef
21.
Cheng, X., Ding, M., Du, D.H., Jia, X.: Virtual backbone construction in multihop ad hoc wireless networks. Wireless Comm. Mobile Comput. 6, 183–190 (2006)CrossRef
22.
Cheng, X., Huang, X., Li, D., Wu, W., Du, D.-Z.: A polynomial-time approximation scheme for minimum connected dominating set in ad hoc wireless networks. Networks 42(2), 202–208 (2003)MathSciNetMATHCrossRef
23.
24.
25.
Colbourn, C.J., Stewart, L.K.: Permutation graphs: connected domination and Steiner trees. Disc. Math. 86(1–3), 179–189 (1990)MathSciNetMATHCrossRef
26.
Dai, F., Wu, J.: An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Trans. Parallel Distrib. Syst. 15(10), 908–920 (2004)CrossRef
27.
Dai, D., Yu, C.: A (5 + ε)-approximation algorithm for minimum weighted dominating set in unit disk graph. Theor. Comput. Sci. 410, 756–765 (2009)MathSciNetMATHCrossRef
28.
Deering, S., Farinacci, D., Jacobson, V., Lui, C.-G., Wei, L.: An architecture for wide area multicast routing. In: Proceedings of ACM SIGCOMM 1994, pp. 126–135 (1994)CrossRef
29.
Ding, L., Wu, W., Willson, J.K., Du, H., Lee, W.: Construction of directional virtual backbones with minimum routing cost in wireless networks. In: 30th Annual Joint Conference of IEEE Communication and Computer Society (INFOCOM), pp. 1557–1565 (2011)
30.
Ding, L., Wu, W., Willson, J.K., Du, H., Lee, W.: Efficient virtual backbone construction with routing cost constraint in wireless networks using directional antennas. IEEE Trans. Mobile Comput. 11(7), 1102–1112 (2012)CrossRef
31.
Ding, L., Gao, X., Wu, W., Lee, W., Zhu, X., Du, D.-Z.: An exact algorithm for minimum CDS with shortest path constraint in wireless networks. Optim. Lett. (2010) published online
32.
Ding, L., Gao, X., Wu, W., Lee, W., Zhu, Xu, Du, D.-Z.: Distributed construction of connected dominating sets with minimum routing cost in wireless network. In: Proceedings of the 30th International Conference on Distributed Computing Systems (ICDCS), pp. 448–457 (2010)
33.
Ding, L., Wu, W., Willson, J.K., Du, H., Lee, W., Du, D.-Z.: Efficient algorithms for topology control problem with routing cost constraints in wireless networks. IEEE. Trans. Parallel. Distr. Syst. 22(10), 1601–1609 (2011)CrossRef
34.
Ding, L., Wu, W., Willson, J.K., Wu, L., Lu, Z., Lee, W.: Constant-approximation for target coverage problem in wireless sensor networks. In: Proceedings of the 31st Annual Joint Conference of IEEE Communication and Computer Society (INFOCOM) (2012)
35.
Douglas, R.J.: NP-completeness and degree restricted spanning trees. Disc. Math. 105(1–3), 41–47 (1992)MATHCrossRef
36.
Du, D.-Z., Ko, K.-I., Hu, X.: Design and Analysis of Approximation Algorithms. Springer, Berlin (2011)
37.
Du, H., Pardalos, P.M., Wu, W., Wu, L.: Maximum lifetime connected coverage with two active-phase sensors. J. Global Optim. (2012), on line
38.
Du, D.-Z., Thai, M.Y., Li, Y., Liu, D., Zhu, S.: Strongly connected dominating sets in wireless sensor networks with unidirectional links. APWeb, pp. 13–24 (2006)
39.
Du, H., Wu, W., Ye, Q., Li, D., Lee, W., Xu, X.: CDS-based virtual backbone construction with guaranteed routing cost in wireless sensor networks. IEEE Trans. Parallel Distr. Syst., to appear
40.
Du, D.-Z., Graham, R.L., Pardalos, P.M., Wan, P.J., Wu, W., Zhao, W.: Analysis of greedy approximation with nonsubmodular potential functions. In: Proceedings of SODA (2008)
41.
Du, H., Ye, Q., Zhong, J., Wang, A., Lee, W., Park, H.: PTAS for minimum connected dominating set with routing cost constraint in wireless sensor networks. In: 4th Annual International Conference on Combinatorial Optimization and Applications (COCOA) (2010)
42.
Du, H., Wu, W., Lee, W., Liu, Q., Zhang, Z., Du, D.-Z.: On minumum submodular cover with submodular cost. J. Global Optim. 50(2), 229–234 (2011)MathSciNetMATHCrossRef
43.
Du, H., Ye, Q., Wu, W., Lee, W., Li, D., Du, D.-Z., Howard, S.: Constant approximation for virtual backbone construction with guaranteed routing cost in wireless sensor networks. INFOCOM, pp. 1737–1744 (2011)
44.
Duchet, P., Meyniel, H.: On Hadwiger’s number and stability numbers. Annal. Disc. Math. 13, 71–74 (1982)MathSciNetMATH
45.
Eriksson, H.: MBone: the multicast backbone. Commun. ACM (1994)
46.
Erlebach, T., Mihalák, M.: A (4 + ε)-approximation for the minimum-weight dominating set problem in unit disk graphs. WAOA, pp. 135–146 (2009)
47.
48.
Feige, U., Halldórsson, M.M., Kortsarz, G., Srinivasan, A.: Approximating the domatic number. SIAM J. Comput. 32(1), 172–195 (2002)MathSciNetMATHCrossRef
49.
Fodor, F.: The densest packing of 13 congruent circles in a circle. Beitrage Algebra Geom. 44(2), 431–440 (2003)MathSciNetMATH
50.
Folkman, J.H., Graham, R.L.: A packing inequality for compact convex subsets of the plane. Canad. Math. Bull. 12, 745–752 (1969)MathSciNetMATHCrossRef
51.
Funke, S., Kesselman, A., Meyer, U., Segal, M.: A simple improved distributed algorithm for minimum CDS in unit disk graphs. ACM Trans. Sensor Net. 2, 444–453 (2006)CrossRef
52.
Fujito, T.: Approximation algorithms for submodular set cover with application, IEICE Trans. Inf. Syst. E83-D(3), 480–487 (2000)
53.
Gao, X., Huang, Y., Zhang, Z., Wu, W.: (6+epsilon)-approximation for minimum weight dominating set in unit disk graphs. COCOON, pp. 551–557 (2008)
54.
Gao, X., Wang, Y., Li, X., Wu, W.: Analysis on theoretical bounds of approximating dominating set problems. Disc. Math. Algorithms Appl. 1(1), 71–84 (2009)MathSciNetMATHCrossRef
55.
Garg, N., Könemann, J.: Faster and simpler algorithms for multicommodity flows and other fractional packing problems. In: Proceedings of 39th Annual Symposium on the Foundations of Computer Science (FOCS), pp. 300–309 (1998)
56.
57.
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman and Sons, San Francisco, CA (1979)MATH
58.
Gfeller, B., Vicari, E.: A faster distributed approximation scheme for the connected dominating set problem for growth-bounded graphs. In: Proceedings of the 6th Ad-Hoc, Mobile, and Wireless Networks International Conference (ADHOC-NOW 2007). Lecture Notes in Computer Science, vol. 4686, pp. 59–73. Springer, Berlin (2007)
59.
Gibson, M., Pirwani, I.: Algorithms for dominating set in disk graphs: breaking the logn barrier. Algorithms–ESA, pp. 243–254 (2010)
60.
Green, P.E.: Fiber-Optic Networks. Prentical-Hall, Cambrige, MA (1992)
61.
62.
63.
Guha, S., Khuller, S.: Improved methods for approximating node weighted Steiner trees and connected dominating sets. Springer Lect. Notes Comput. Sci. 1530, 54–66 (1998)CrossRef
64.
Hahn, R., Reichl, H.: Batteries and power supplies for wearable and ubiquitous computing. In: Proceedings of the 3rd International Symposium on Wearable Computers (1999)
65.
Hoppe, R.: Bemerkungen de redaktion. Grunert Arch. Math. Phys. 56, 307–312 (1874)
66.
Huang, Y., Gao, X., Zhang, Z., Wu, W.: A better constant-factor approximation for weighted dominating set in unit disk graph. J. Combin. Optim. 18(2), 179–194 (2009)MathSciNetMATHCrossRef
67.
Kim, D., Wu, Y., Li, Y., Zou, F., Du, D.-Z.: Constructing minimum connected dominating sets with bounded diameters in wireless networks. IEEE Trans. Parallel Distrib. Syst. 20(2), 147–157 (2009)CrossRef
68.
Kim, D., Zhang, Z., Li, X., Wang, W., Wu, W., Du, D.-Z.: A better approximation algorithm for computing connected dominating sets in unit ball graphs. IEEE Trans. Mobile Comput. 9(8), 1108–1118 (2010)CrossRef
69.
Klein, P.N., Ravi, R.: A nearly best-possible approximation for node-weighted Steiner trees. J. Algorithms 19, 104–115 (1995)MathSciNetMATHCrossRef
70.
Kuhn, F., Zollinger, A.: Ad-hoc networks beyond unit disk graphs. In: Proceedings of the Joint Workshop of Foundation of Mobile Computing (DIALM-POMC) (2003)
71.
Laskar, R., Pfaff, J.: Domination and irredundance in split graphs. Technical Report 430, Department of Mathematical Sciences, Clemson University (1983)
72.
Li, M., Wan, P.J., Yao, F.F.: Tighter approximation bounds for minimum CDS in wireless ad hoc networks. ISAAC’2009. Lecture Notes in Computer Science, vol. 5878, pp. 699–709 (2009)CrossRef
73.
Li, D., Du, X., Hu, X., Jia, X.: Minimizing number of wavelengths in multicast routing trees in WDM networks. Networks 35(4), 260–265 (2000)CrossRef
74.
Li, Y., Thai, M.T., Wang, F., Du, D.-Z.: On the construction of a strongly connected broadcast arborescence with bounded transmission delay. IEEE Trans. Mobile Comput. 5(10), 1460–1470 (2006)CrossRef
75.
Li, Y., Thai, M.Y., Wang, F., Yi, C.-W., Wan, P.-J., Du, D.-Z.: On greedy construction of connected dominating sets in wireless networks. Wireless Commun. Mobile Comput. 5, 927–932 (2005)CrossRef
76.
Li, D., Du, H., Wan, P.-J., Gao, X., Zhang, Z., Wu, W.: Minimum power strongly connected dominating sets in wireless networks. In: Proceedings of the 2008 International Conference on Wireless Networks (ICWN’08) (2008)
77.
Li, D., Du, H., Wan, P.-J., Gao, X., Zhang, Z., Wu, W.: Construction of strongly connected dominating sets in asymmetric multihop wireless networks. Theoret. Comput. Sci. 410(8–10), 661–669 (2009)MathSciNetMATHCrossRef
78.
Liu, Q., Li, X., Wu, L., Du, H., Zhang, Z., Wu, W., Xu, Y.: A new proof for Zassenhaus–Groemer–Oler inequality. Disc. Math. Algorithms Appl. (2012), to appear
79.
Min, M., Du, H., Jiao, X., Huang, X., Huang, S.C.-H., Wu, W.: Improving construction for connected dominating set with Steiner tree in wireless sensor networks. J. Global Optim. 35, 111–119 (2006)MathSciNetMATHCrossRef
80.
Moscibroda, T., Wattenhofer, R.: Maximizing the lifetime of dominating sets. In: Proceedings of the 5th IEEE International Workshop on Algorithms for Wireless, Mobile, Ad hoc and Sensor Networks (2005)
81.
Mukherjee, B.: WDM-based local lightwave networks Part I: single-hop system. IEEE Networks 3, 12–26 (1992)CrossRef
82.
Mukherjee, B.: WDM-based local lightwave networks Part II: multihop system. IEEE Networks 4, 22–32 (1992)
83.
84.
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1999)MATH
85.
86.
Pandit, S., Pemmaraju, S.V., Varadarajan, K.R.: Approximation algorithms for domatic partitions of unit disk graphs. In: Dinur, L. et al. (eds.) APPROX and RANDOM 2009. Lecture Notes in Computer Science, vol. 5687, pp. 312–325 (2009)MathSciNetCrossRef
87.
Ramamurthy, B., Iness, J., Mukherjee, B.: Minimizing the number of optical amplifiers needed to support a multi-wavelength optical LAN/MAN. In: Proceedings of IEEE INFOCOM’97, pp. 261–268 (1997)
88.
Ramaswami, R., Sasaki, G.: Multiwavelength optical networks with limited wavelength conversion. IEEE/ACM Trans. Networking 6(6), 744–754 (1998)CrossRef
89.
Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of 28th STOCS (1997)
90.
Ruan, L., Du, D.-Z., Hu, X., Jia, X., Li, D.: Approximations for color-covering problems. In: Proceedings of 1st International Congress of Chinese Mathematicians, pp. 503–507. Beijing, China (1998)
91.
Ruan, L., Du, D.-Z., Hu, X., Jia, X., Li, D., Sun, Z.: Converter placement supporting broadcast in WDM optical networks. IEEE Trans. Comput. 50(7), 750–758 (2001)MathSciNetCrossRef
92.
Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., Ko, K.-I.: A greedy approximation for minimum connected dominating set. Algorithmca, 329(1–3), 325–330 (2004)MathSciNetMATH
93.
Salhieh, A., Weinmann, J., Kochha, M., Schwiebert, L.: Power efficient topologies for wireless sensor networks. ICPP’2001, pp. 156–163 (2001)
94.
Sampathkumar, E., Walikar, H.B.: The connected domination number of a graph. J. Math. Phys. Sci. 13(6), 607–613 (1979)MathSciNetMATH
95.
Sivakumar, R., Das, B., Bharghavan, V.: An improved spine-based infrastructure for routing in ad hoc networks. In: IEEE Symposium on Computer and Communications, Athens, Greece (1998)
96.
Slijepcevic, S., Potkonjak, M.: Power efficient organization of wireless sensor networks. IEEE International Conference on Communications, pp. 472–476 (2001)
97.
Solis-Oba, R.: 2-approximation algorithm for finding a spanning tree with maximum number of leaves. In: Proceedings of 6th European Symposium on Algorithms (ESA’98). Lecture Notes in Computer Science, vol. 1461, pp. 441–452. Springer, Berlin (1998)
98.
Srinivasan, A., Wu, J.: TRACK: A novel connected dominating set based sink mobility model for WSNs. ICCCN, pp. 664–671 (2008)
99.
Stojmenovic, I., Seddigh, M., Zunic, J.: Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks. In: Proceedings of IEEE Hawaii International Conference on System Sciences (2001)
100.
Sum, J., Wu, J., Ho, K.: Analysis on a localized pruning method for connected dominating sets. J. Inf. Sci. Eng. 23(4), 1073–1086 (2007)MathSciNet
101.
Thai, M.T., Du, D.-Z.: Connected dominating sets in disk graphs with bidirectional links. IEEE Commun. Lett. 10(3), 138–140 (2006)CrossRef
102.
Thai, M.Y., Wang, F., Liu, D., Zhu, S., Du, D.-Z.: Connected dominating sets in wireless networks with different communication ranges. IEEE Trans. Mobile Comput. 6(7), 721–730 (2007)CrossRef
103.
Vahdatpour, A., Dabiri, F., Moazeni, M., Sarrafzadeh, M.: Theoretical bound and practical analysis of connected dominating set in ad hoc and sensor networks. In: Proceedings of 22nd International Symposium on Distributed Computing (DISC), pp. 481–495 (2008)
104.
Wan, P.J., Alzoubi, K.M., Frieder, O.: Distributed construction of connected dominating set in wireless ad hoc networks. ACM/Springer Mobile Network. Appl. 9(2), 141–149 (2004). A preliminary version of this paper appeared in IEEE INFOCOM (2002)
105.
Wan, P.-J., Alzoubi, K.M., Frieder, O.: A simple heuristic for minimum connected dominating set in graphs. Int. J. Found. Comput. Sci. 14(2), 323–333 (2003)MathSciNetMATHCrossRef
106.
Wan, P.J., Wang, L., Yao, F.F.: Two-phased approximation algorithms for minimum CDS in wireless ad hoc networks. IEEE ICDCS, pp. 337–344 (2008)
107.
Wan, P.-J., Xu, X., Wang, Z.: Wireless coverage with disparate ranges. ACM Mobihoc (2011)
108.
Wan, P.-J., Du, D.-Z., Pardalos, P.M., Wu, W.: Greedy approximations for minimum submodular cover with submodular cost. Comput. Optim. Appl. 45(2), 463–474 (2010)MathSciNetMATHCrossRef
109.
Wan, P.J., Huang, S.C.-H., Wang, L., Wan, Z., Jia, X.: Minimum-latency aggregation scheduling in multihop wireless networks. ACM MOBIHOC (2009)
110.
Wan, P.-J., Wang, Z., Wan, Z., Huang, S.C.-H., Liu, H.: Minimum-latency schedulings for group communications in multi-channel multihop wireless networks. WASA (2009)
111.
Wang, F., Thai, M.T., Du, D.-Z.: On the construction of 2-connected virtual backbone in wireless networks. IEEE Trans. Wireless Commun. 8(3), 1230–1237 (2009)CrossRef
112.
Wang, L., Wan, P.-J., Yao, F.F.: Minimum CDS in multihop wireless networks with disparate communication ranges, WASA (2010)
113.
White, K., Parber, M., Pulleyblank, W.: Steiner trees, connected domination and strongly chordal graphs. Networks 15(1), 109–124 (1985)MathSciNetMATHCrossRef
114.
Willson, J.K., Ding, L., Wu, W., Wu, L., Lu, Z., Lee, W.: A better constant-approximation for coverage problem in wireless sensor networks, preprint.
115.
Willson, J.K., Gao, X., Qu, Z., Zhu, Y., Li, Y., Wu, W.: Efficient distributed algorithms for topology control problem with shortest path constraints. Disc. Math. Algorithms Appl. 1, 437–461 (2009)MathSciNetMATHCrossRef
116.
117.
Wu, J., Li, H.: On calculating connected dominating set for efficient routing in ad hoc wireless networks. In: Proceedings of the 3rd ACM International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 7–14 (1999)
118.
Wu, J., Dai, F.: Virtual backbone construction in MANETs using adjustable transmission ranges. IEEE Trans. Mob. Comput. 5(9), 1188–1200 (2006)CrossRef
119.
Wu, J., Gao, M., Stojmenovic, I.: On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks. ICPP pp. 346–356 (2001)
120.
Wu, J., Wu, B., Stojmenovic, I.: Power-aware broadcasting and activity scheduling in ad hoc wireless networks using connected dominating sets. Wireless Commun. Mobile Comput. 3(4), 425–438 (2003)CrossRef
121.
Wu, J., Dai, F., Yang, S.: Iterative local solutions for connected dominating set in ad hoc wireless networks, MASS (2005)
122.
Wu, J., Lou, W., Dai, F.: Extended multipoint relays to determine connected dominating sets in MANETs. IEEE Trans. Comput. 55(3), 347–337 (2006)CrossRef
123.
Wu, W., Du, H., Jia, X., Li, Y., Huang, S.C.-H.: Minimum connected dominating sets and maximal independent sets in unit disk graphs, Theor. Comput. Sci. 352(1–3), 1–7 (2006)MathSciNetMATHCrossRef
124.
Xing, K., Cheng, W., Park, E.K., Rotenstreich, S.: Distributed connected dominating set construction in geometric k-disk graphs. IEEE ICDCS, pp. 673–680 (2008)
125.
126.
Zhang, Y., Li, W.: Modeling and energy consumption evaluation of a stochastic wireless sensor networks. preprint (2011)
127.
Zhang, Z., Gao, X., Wu, W., Du, D.-Z.: A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks. J. Global Optim. 45(3), 451–458 (2009)MathSciNetMATHCrossRef
128.
Zhang, N., Shin, I., Zou, F., Wu, W., Thai, M.T.: Trade-off scheme for fault tolerant connected dominating sets on size and diameter. FOWANC, pp. 1–8 (2008)
129.
Zhao, Y., Wu, J., Li, F., Lu, S.: VBS: Maximum lifetime sleep scheduling for wireless sensor networks using virtual backbones, INFOCOM pp. 366–370 (2010)
130.
Zhong, C.: Sphere Packing. Springer, Berlin (1999)
131.
Zhong, X., Wang, J., Hu, N.: Connected dominating set in 3-dimensional space for ad hoc network. In: Proceedings of IEEE Wireless Communications and Networking Conference (WCNC’07) (2007)
132.
Zou, F., Li, X., Kim, D., Wu, W.: Construction of minimum connected dominating set in 3-dimensional wireless networks. In: Proceedings of Third International Conference on Wireless Algorithms, Systems and Applications (WASA 08) (2008)
133.
Zou, F., Li, X., Gao, S., Wu, W.: Node-weighted Steiner tree approximation in unit disk graphs. J. Combin. Optim. 18(4), 342–349 (2009)MathSciNetMATHCrossRef
134.
Zou, F., Wang, Y., Xu, X., Du, H., Li, X., Wan, P., Wu, W.: New approximations for weighted dominating sets and connected dominating sets in unit disk graphs. Theoret. Comput. Sci. 412(3), 198–208 (2011)MathSciNetMATHCrossRef
Metadaten
Titel
Routing-Cost Constrained CDS
verfasst von
Ding-Zhu Du
Peng-Jun Wan
Copyright-Jahr
2013
Verlag
Springer New York
Buch
Connected Dominating Set: Theory and Applications

Print ISBN: 978-1-4614-5241-6

Electronic ISBN: 978-1-4614-5242-3

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-1-4614-5242-3_7