几类组合优化问题的算法研究
|
摘要
组合最优化是指在给定的有限集中,找出按某种目标达到最优的解的一类问题,常见的组合优化问题很多都是NP-困难的.本论文主要研究三类NPˉ困难的优化问题的算法.第二章研究3ˉ连通图3ˉ正则图的最长圈问题,通过组合方法构造出一个长度至少为|G|r的一个圈,其中r≈0.8为方程8.956r+1.036r=10.992r的实数根.这也改进了Jackson等人[40]中的r≈0.753的结论.
第三章和第四章研究控制集问题,设G为图, D为G的一个点子集,如果G D中任意一个点都和D中某个点相邻且G[D]连通,则称D为G的一个连通控制集.αMOC-CDS指G的一个连通控制集D满足对任意G的两个点u, v, G中最短的连接u,v的且内部点都在D中的路的长度不超过G中最短(u,v)-路的长度的α倍. Du等人[21]给出了单位圆盘图上α≥5时的一个常数比近似算法.本文第三章考虑α <5的情况,首先给出单位圆盘图上的一个常数比近似算法,然后利用这个算法得到一个多项式时间近似模式算法.
设D为G的一个连通控制集,如果对G D中每个点u, D中至少存在k个点到u的距离不超过r,则称D为G的一个r-跳k-连通控制集,简记为(k,r)-连通控制集,第四章首先给出单位圆盘图上(k,r)ˉ控制集的一个两阶段算法,其近似比只与k,r有关,然后对一般图给出一个贪婪算法,其近似比为2rH(r+k r),其中H(·)为调和函数, r为幂图Gr的最大度.
In a Combinatorial Optimization Problem, one is required to find an element in afinite set such that the objective function on this element is minimum or maximum. Manycombinatorial optimization problems are NP-hard. Three problems are considered in thisthesis. In Chapter2, we find a circle in a3-connected3-regular graph G of length at least|G|rby construction, where r≈0.8is the real root of8.956r+1.036r=10.992r. Thisresult improves the previous work of Jackson [40] in which r≈0.753.
In Chapter3and Chapter4, dominating set problems are considered. Let G be agraph, a vertex subset D of G is said to be a connected dominating set of G, if everyvertex of G D has at least one neighbor in D and G[D], the subgraph induced by D,is connected. A connected dominating set D is called an αMOC-CDS if for any vertexu, v of G, there is an (u, v)-path of G whose internal vertices lie in D and whose lengthis at most α times the length of the shortest (u, v)-path in G. In [21], Du et. al. gavea constant factor approximation algorithm on unit disk graph for the case α≥5. InChapter3, we consider the case α <5and give two approximation algorithms on unitdisk graphs. The first one is a constant factor approximation algorithm. The second oneis a polynomial time approximation scheme based on the first one.
Let D be a connected dominating set of G. If for any vertex u of G D, there are atleast k vertices in D which are at most r hops away from u, then D is called a connectedr-hop k-dominating set, or (k, r)-CDS for short. In Chapter4, Two approximation al-gorithms for (k, r)-CDS problem are presented. The first one is a two-step algorithm onunit disk graphs whose approximation ratio only depends on k and r. The second oneis a greedy algorithm on general graphs whose approximation ratio is2rH(r+k r),where H(·) is harmonic function, ris the maximum degree in the power graph Gr.
第三章和第四章研究控制集问题,设G为图, D为G的一个点子集,如果G D中任意一个点都和D中某个点相邻且G[D]连通,则称D为G的一个连通控制集.αMOC-CDS指G的一个连通控制集D满足对任意G的两个点u, v, G中最短的连接u,v的且内部点都在D中的路的长度不超过G中最短(u,v)-路的长度的α倍. Du等人[21]给出了单位圆盘图上α≥5时的一个常数比近似算法.本文第三章考虑α <5的情况,首先给出单位圆盘图上的一个常数比近似算法,然后利用这个算法得到一个多项式时间近似模式算法.
设D为G的一个连通控制集,如果对G D中每个点u, D中至少存在k个点到u的距离不超过r,则称D为G的一个r-跳k-连通控制集,简记为(k,r)-连通控制集,第四章首先给出单位圆盘图上(k,r)ˉ控制集的一个两阶段算法,其近似比只与k,r有关,然后对一般图给出一个贪婪算法,其近似比为2rH(r+k r),其中H(·)为调和函数, r为幂图Gr的最大度.
In a Combinatorial Optimization Problem, one is required to find an element in afinite set such that the objective function on this element is minimum or maximum. Manycombinatorial optimization problems are NP-hard. Three problems are considered in thisthesis. In Chapter2, we find a circle in a3-connected3-regular graph G of length at least|G|rby construction, where r≈0.8is the real root of8.956r+1.036r=10.992r. Thisresult improves the previous work of Jackson [40] in which r≈0.753.
In Chapter3and Chapter4, dominating set problems are considered. Let G be agraph, a vertex subset D of G is said to be a connected dominating set of G, if everyvertex of G D has at least one neighbor in D and G[D], the subgraph induced by D,is connected. A connected dominating set D is called an αMOC-CDS if for any vertexu, v of G, there is an (u, v)-path of G whose internal vertices lie in D and whose lengthis at most α times the length of the shortest (u, v)-path in G. In [21], Du et. al. gavea constant factor approximation algorithm on unit disk graph for the case α≥5. InChapter3, we consider the case α <5and give two approximation algorithms on unitdisk graphs. The first one is a constant factor approximation algorithm. The second oneis a polynomial time approximation scheme based on the first one.
Let D be a connected dominating set of G. If for any vertex u of G D, there are atleast k vertices in D which are at most r hops away from u, then D is called a connectedr-hop k-dominating set, or (k, r)-CDS for short. In Chapter4, Two approximation al-gorithms for (k, r)-CDS problem are presented. The first one is a two-step algorithm onunit disk graphs whose approximation ratio only depends on k and r. The second oneis a greedy algorithm on general graphs whose approximation ratio is2rH(r+k r),where H(·) is harmonic function, ris the maximum degree in the power graph Gr.
引文
[1] R. E. L. Aldred, D. A. Holton and C. Thomassen, Cycles through four edges in3-connected cubic graphs[J]. Graphs and Combinatorics1(1985)7-11.
[2] R. E. L. Aldred and D. A. Holton, Cycles through five edges in3-connected cubicgraphs[J]. Graphs and Combinatorics,3(1987)299-311.
[3] R. E. L. Aldred, S. Bau, D. A. Holton, and B. D. McKay, Cycles through23verticesin3-connected cubic planar graphs[J]. Graphs and Combinatorics15(1999)373-376.
[4] K.M. Alzoubi, P.J. Wan and O. Frieder, Message-optimal connected dominating setsin mobile ad hoc networks[C], ACM Mobilhoc2002,157-164.
[5] A.D. Amis, R. Prakash, T.H.P. Vuong and D.T. Huynh, Max-min d-cluster formationin wireless ad hoc networks[J]. IEEE INFOCOM2002,32-41.
[6] D. Barnette, Trees in polyhedral graphs[J]. Canad. J. Math.18(1966)731-736.
[7] S. Bau and D. A. Holton, Cycles containing12vertices in3-connected cubic graphs[J].J. Graph Theory15(1991)421-429.
[8] V. Bharghavan and B. Das, Routing in ad hoc networks using minimum connecteddominating sets[C], International Conference on Communication, Montreal, Canada(1997).
[9] M. Bilinski, B. Jackson, J. Ma and X. Yu, Circumference of3-connected claw-freegraphs and large Eulerian subgraphs of3-edge connected graphs[J]. J. Combin. The-ory Ser. B101(2011)214-236.
[10] J. A. Bondy and M. Simonovits, Longest cycles in3-connected3-regular graphs[J].Canad. J. Math.32(1980)987-992.
[11] J. Blum, M. Ding, A. Thaeler and X.Z. Cheng, Connected dominating set in sensornetworks and MANETs, Handbook of Combinatorial Optimization[M], D.Z. Du andP. Pardalos Eds, Kluwer Academic Publishers2004,329-369.
[12] M. Cadei, X.Z. Cheng and D.Z. Du, Connected domination in ad hoc wireless net-works[C]. Proc.6th International Conference on Computer Science and Informatics2002.
[13] X.Z. Cheng, X. Huang, D.Y. Li, W.L. Wu and D.Z. Du, Polynomial-time approxima-tion scheme for minimum connected dominating set in ad hoc wireless networks[J].Networks42(2003)202-208.
[14] B.N. Clark, C.J. Colbourn and D.S. Johnson, Unit disk graphs[J]. Discrete Mathe-matics86(1990)165-177.
[15] S. Cook, The complexity of theorem proving procedures[C]. Proceedings of the ThirdAnnual ACM Symposium on Theory of Computing (1971)151–158.
[16] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms,Second Edition[M]. McGraw-Hill Higher Education2002.
[17] G. B. Dantzig, On the significance of solving linear programming problems with someinteger variables[J], Econometrica28(1960)30-44.
[18] G. B. Dantzig, W. O. Blattner and M. R. Rao, All shortest routes from a fixed originin a graph, Theory of Graph: International Symposium, Gordon and Breach[M]. NY1967,85-90.
[19] B. Das, V. Bharghavan, Routing in ad hoc networks using minimum connected dom-inating sets[C], Proc. IEEE International Conference on Communications1,1997,376-380.
[20] L. Ding, X.F. Gao, W.L. Wu, W.J. Lee, X. Zhu and D.-Z. Du, Distributed contructionof connected dominating sets with minimum routing cost in wireless network[C].IEEE International Conference on Distributed Computing Systerms (2010)448-457.
[21] L. Ding, W.L. Wu, J. Willson, H.J. Du, W.J. Lee, and D.-Z. Du, Efcient algorithmsfor topology control problem with routing cost constraint in wireless networks[J].22(2011)1601-1609.
[22] H.J. Du, W.L. Wu, W.J. Lee, Q.H. Liu, Z. Zhang and D.-Z. Du, On minimumsubmodular cover with submodular cost[J], J. Global Optimization50(2011)229-234.
[23] H.W. Du, Q. Ye, J.F. Zhong, Y.X. Wang, W.J. Lee and H. Park, PTAS for minimumconnected dominating set with routing cost constraint in wireless sensor networks[J].Lecture Notes in Computer Science6508(2010)252-259.
[24] J. Edmonds, Covers and packing s in a family of sets[J]. Bull. Amer. Math. Soc68(1962)494-499.
[25] J. Edmonds, Paths, trees and flowers[J]. Canad. J. Math.17(1965)449-467.
[26] M. N. Ellingham, D. A. Holton and C. H. C. Little, Cycles through10vertices in3-connected cubic graphs[J]. Combinatorica4(1984)265-273.
[27] A. Ephremides, J. Wieselthier and D. Baker, A design concept for reliable mobileradio networks with frequency hopping signaling[J]. Proc. IEEE75(1987)56-73.
[28] J. L. Fouquet and H. Thuillier, Cycles through given vertices in planar3-connectedcubic graphs[J]. Ars Combinatoria20B (1985)75-105.
[29] S. Funke, A. Kesselman, U. Meyer and M. Segal, A simple improved distributedalgorithm for minimum CDS in unit disk graphs[J]. ACM Transactions on SensorNetorks2(2006)444-453.
[30] X.F. Gao, Y.X. Wang, X.Y. Li and W.L. Wu, Analysis on theoretical bounds forapproximating dominating set problems[J]. Discrete Mathematics, Algorithms andApplications1(2009)71-84.
[31] X.F. Gao, X.Y. Li and W.L. Wu, A constant-factor approximation for d-hop con-nected dominating sets in unit disk graph[C]. Proceedings of the Tenth InternationalConference on Information and Management Sciences2011.
[32] B. Gao, Y.H. Yang, H.Y. Ma, An efcient approximation scheme for minimum con-nected dominating set in wireless ad hoc networks[C]. IEEE Vehicular Technologyconference, Los Angeles CA4(2004)2744-2748.
[33] M.R. Garey and D.S. Johnson, Computers and intractability: a guide to the theoryof NP-completeness[M]. Freeman, San Francisco1978.
[34] M. Gerla and J.T.C. Tsai, Multicluster, mobile, multimedia radio network[J]. Wire-less Networks1(1995)255-265.
[35] J. F. Gimpel, A method of producing a boolean function having an arbitrarily pre-scribed prime implicant table[J], IEEE Trans. Computers14(1965)485-588.
[36] S. Guha and S. Khuller, Approximation algorithms for connected dominating set[J].Algorithmica20(1998)374-387.
[37] B. Han, W.J. Jia, Design and analysis of connected dominating set formation fortopology control in wireless ad hoc networks[C]. Proc14th International Conferenceon Computer Communications and Networks (ICCCN2005)(2005)7-12.
[38] D. A. Holton, Cycles in3-connected cubic planar graphs[J]. Ann. Discrete Math.27(1985)219-226.
[39] H.B. Hunt III, M.V. Marathe, V. Radhakrishnan, S.S. Ravi, D.J. Rosenkrantz andR.E. Stearns, NC-approximation schemes for NP-and PSPACE-hard problems forgeometric graphs[J]. J. Algorithms26(1998)238-274.
[40] B. Jackson, Longest cycles in3-connected cubic graphs[J]. J. Combin. Theory Ser.B41(1986)17-26.
[41] Y.S. Li, M.T. Thai, F. Wang, C.W. Yi, P.J. Wan and D.Z. Du, On greedy construc-tion of connected dominating sets in wireless networks[J]. Wiley Journal on WirelessCommunications and Mobile Computing5(2005)927-932.
[42] D. Li, L. Liu and H. Yang, Minimum connected r-hop k-dominating set in wirelessnetworks[J]. Discrete Mathematics, Algorithms and Applications1(2009)45-58.
[43] L. Lov′asz, Problem5[J], Period. Math. Hung4(1974)53-62.
[44] M. Min, H.W. Du, X.H. Jia, C.X. Huang, S.C.H. Huang and W.Li. Wu, Improv-ing construction of connected dominating set with Steiner tree in wireless sonesornetworks[J]. Journal of Global Optimaization35(2006)111-119.
[45] T.N. Nguyen and D.T. Huynh, Connected d-hop dominating sets in mobile ad hocnetworks[C].4th International Symposium on Modeling and Optimization in Mobile,Ad Hoc and Wireless Networks (2006)1-8.
[46] F.G. Nocetti, J.S. Gonzalez and I. Stojmenovic, Connectivity based k-hop clusteringin wireless networks[J]. Telecommunication Systems22(2003)205-220.
[47] M.Q. Rieck, S. Pai and S. Dhar, Distributed routing algorithms for multi-hop ad hocnetworks using d-hop connected d-dominating sets[J]. Computer Networks47(2005)785-799.
[48] L. Ruan, H.W. Du, X.H. Jia, W.L. Wu, Y.S. Li and K. Ko, A greedy approximationfor minimum connected dominating sets[J]. Theoretical Computer Science329(2004)325-330.
[49] M.A. Spohn and J.J. Garcia-Luna-Aceves, Improving broadcast operations in ad hocnetworks using two-hop connected dominating sets[C]. Proc. IEEE Global Telecom-munications Conference Workshops (2004)147-152.
[50] M.A. Spohn and J.J. Garcia-Luna-Aceves, Bounded-distance multi-clusterhead for-mation in wireless ad hoc networks, Ad Hoc Networks5(2007)505-530.
[51] P. G. Tait, Remarks on colouring maps[J]. Proc. Roy. Soc. Edinburgh Ser. A10(1880)729.
[52] W. T. Tutte, On Hamilton circuits[J]. J. London Math. Soc.21(1946)98-101.
[53] P.J. Wan, K.M. Alzoubi and O. Frieder, Distributed construction of connecteddominating set in wireless ad hoc networks, Mobile Networks and Applications[M].ACM/Springer9(2002)141-149.
[54] P.J. Wan, L. Wang and F.F. Yao, Two-phased approximation algorithms for min-imum CDS in wireless ad hoc networks[C]. the28th International Conference onDistributed Computing Systems (2008)337-344.
[55] W. Wang, D. Kim, N. Sohaee, C. Ma and W. Wu, A PTAS for minimum d-hopunderwater sink placement problem in2-D underwater sensor networks[J]. DiscreteMathematics, Algorithms and Applications1(2009)283-290.
[56] G. Wegner,U¨ber endliche Kreispackungen in der Ebene[J]. Studia Sci. Math. Hungar.21(1986)1-28.
[57] W.L. Wu, H.W. Du, X.H. Jia, Y.S. Li and S.C. Huang, Minimum connected dominat-ing sets and maximal independent sets in unit disk graphs[J]. Theoretical ComputerScience352(2006)1-7.
[58] J. Wu, H. Li, On calculating connected dominating set for efcient routing in adhoc wireless networks. Proc[C].3rd ACM Int. Workshop on Discrete Algorithms andMethods for Mobile Computing and Communications1999,7-14.
[59] Z. Zhang, X.F. Gao, W.L. Wu and D.Z Du, A PTAS for minimum connected dominat-ing set in3-dimensional wireless sensor networks, Journal of Global Optimization[J].45(2009)451-458.
[2] R. E. L. Aldred and D. A. Holton, Cycles through five edges in3-connected cubicgraphs[J]. Graphs and Combinatorics,3(1987)299-311.
[3] R. E. L. Aldred, S. Bau, D. A. Holton, and B. D. McKay, Cycles through23verticesin3-connected cubic planar graphs[J]. Graphs and Combinatorics15(1999)373-376.
[4] K.M. Alzoubi, P.J. Wan and O. Frieder, Message-optimal connected dominating setsin mobile ad hoc networks[C], ACM Mobilhoc2002,157-164.
[5] A.D. Amis, R. Prakash, T.H.P. Vuong and D.T. Huynh, Max-min d-cluster formationin wireless ad hoc networks[J]. IEEE INFOCOM2002,32-41.
[6] D. Barnette, Trees in polyhedral graphs[J]. Canad. J. Math.18(1966)731-736.
[7] S. Bau and D. A. Holton, Cycles containing12vertices in3-connected cubic graphs[J].J. Graph Theory15(1991)421-429.
[8] V. Bharghavan and B. Das, Routing in ad hoc networks using minimum connecteddominating sets[C], International Conference on Communication, Montreal, Canada(1997).
[9] M. Bilinski, B. Jackson, J. Ma and X. Yu, Circumference of3-connected claw-freegraphs and large Eulerian subgraphs of3-edge connected graphs[J]. J. Combin. The-ory Ser. B101(2011)214-236.
[10] J. A. Bondy and M. Simonovits, Longest cycles in3-connected3-regular graphs[J].Canad. J. Math.32(1980)987-992.
[11] J. Blum, M. Ding, A. Thaeler and X.Z. Cheng, Connected dominating set in sensornetworks and MANETs, Handbook of Combinatorial Optimization[M], D.Z. Du andP. Pardalos Eds, Kluwer Academic Publishers2004,329-369.
[12] M. Cadei, X.Z. Cheng and D.Z. Du, Connected domination in ad hoc wireless net-works[C]. Proc.6th International Conference on Computer Science and Informatics2002.
[13] X.Z. Cheng, X. Huang, D.Y. Li, W.L. Wu and D.Z. Du, Polynomial-time approxima-tion scheme for minimum connected dominating set in ad hoc wireless networks[J].Networks42(2003)202-208.
[14] B.N. Clark, C.J. Colbourn and D.S. Johnson, Unit disk graphs[J]. Discrete Mathe-matics86(1990)165-177.
[15] S. Cook, The complexity of theorem proving procedures[C]. Proceedings of the ThirdAnnual ACM Symposium on Theory of Computing (1971)151–158.
[16] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms,Second Edition[M]. McGraw-Hill Higher Education2002.
[17] G. B. Dantzig, On the significance of solving linear programming problems with someinteger variables[J], Econometrica28(1960)30-44.
[18] G. B. Dantzig, W. O. Blattner and M. R. Rao, All shortest routes from a fixed originin a graph, Theory of Graph: International Symposium, Gordon and Breach[M]. NY1967,85-90.
[19] B. Das, V. Bharghavan, Routing in ad hoc networks using minimum connected dom-inating sets[C], Proc. IEEE International Conference on Communications1,1997,376-380.
[20] L. Ding, X.F. Gao, W.L. Wu, W.J. Lee, X. Zhu and D.-Z. Du, Distributed contructionof connected dominating sets with minimum routing cost in wireless network[C].IEEE International Conference on Distributed Computing Systerms (2010)448-457.
[21] L. Ding, W.L. Wu, J. Willson, H.J. Du, W.J. Lee, and D.-Z. Du, Efcient algorithmsfor topology control problem with routing cost constraint in wireless networks[J].22(2011)1601-1609.
[22] H.J. Du, W.L. Wu, W.J. Lee, Q.H. Liu, Z. Zhang and D.-Z. Du, On minimumsubmodular cover with submodular cost[J], J. Global Optimization50(2011)229-234.
[23] H.W. Du, Q. Ye, J.F. Zhong, Y.X. Wang, W.J. Lee and H. Park, PTAS for minimumconnected dominating set with routing cost constraint in wireless sensor networks[J].Lecture Notes in Computer Science6508(2010)252-259.
[24] J. Edmonds, Covers and packing s in a family of sets[J]. Bull. Amer. Math. Soc68(1962)494-499.
[25] J. Edmonds, Paths, trees and flowers[J]. Canad. J. Math.17(1965)449-467.
[26] M. N. Ellingham, D. A. Holton and C. H. C. Little, Cycles through10vertices in3-connected cubic graphs[J]. Combinatorica4(1984)265-273.
[27] A. Ephremides, J. Wieselthier and D. Baker, A design concept for reliable mobileradio networks with frequency hopping signaling[J]. Proc. IEEE75(1987)56-73.
[28] J. L. Fouquet and H. Thuillier, Cycles through given vertices in planar3-connectedcubic graphs[J]. Ars Combinatoria20B (1985)75-105.
[29] S. Funke, A. Kesselman, U. Meyer and M. Segal, A simple improved distributedalgorithm for minimum CDS in unit disk graphs[J]. ACM Transactions on SensorNetorks2(2006)444-453.
[30] X.F. Gao, Y.X. Wang, X.Y. Li and W.L. Wu, Analysis on theoretical bounds forapproximating dominating set problems[J]. Discrete Mathematics, Algorithms andApplications1(2009)71-84.
[31] X.F. Gao, X.Y. Li and W.L. Wu, A constant-factor approximation for d-hop con-nected dominating sets in unit disk graph[C]. Proceedings of the Tenth InternationalConference on Information and Management Sciences2011.
[32] B. Gao, Y.H. Yang, H.Y. Ma, An efcient approximation scheme for minimum con-nected dominating set in wireless ad hoc networks[C]. IEEE Vehicular Technologyconference, Los Angeles CA4(2004)2744-2748.
[33] M.R. Garey and D.S. Johnson, Computers and intractability: a guide to the theoryof NP-completeness[M]. Freeman, San Francisco1978.
[34] M. Gerla and J.T.C. Tsai, Multicluster, mobile, multimedia radio network[J]. Wire-less Networks1(1995)255-265.
[35] J. F. Gimpel, A method of producing a boolean function having an arbitrarily pre-scribed prime implicant table[J], IEEE Trans. Computers14(1965)485-588.
[36] S. Guha and S. Khuller, Approximation algorithms for connected dominating set[J].Algorithmica20(1998)374-387.
[37] B. Han, W.J. Jia, Design and analysis of connected dominating set formation fortopology control in wireless ad hoc networks[C]. Proc14th International Conferenceon Computer Communications and Networks (ICCCN2005)(2005)7-12.
[38] D. A. Holton, Cycles in3-connected cubic planar graphs[J]. Ann. Discrete Math.27(1985)219-226.
[39] H.B. Hunt III, M.V. Marathe, V. Radhakrishnan, S.S. Ravi, D.J. Rosenkrantz andR.E. Stearns, NC-approximation schemes for NP-and PSPACE-hard problems forgeometric graphs[J]. J. Algorithms26(1998)238-274.
[40] B. Jackson, Longest cycles in3-connected cubic graphs[J]. J. Combin. Theory Ser.B41(1986)17-26.
[41] Y.S. Li, M.T. Thai, F. Wang, C.W. Yi, P.J. Wan and D.Z. Du, On greedy construc-tion of connected dominating sets in wireless networks[J]. Wiley Journal on WirelessCommunications and Mobile Computing5(2005)927-932.
[42] D. Li, L. Liu and H. Yang, Minimum connected r-hop k-dominating set in wirelessnetworks[J]. Discrete Mathematics, Algorithms and Applications1(2009)45-58.
[43] L. Lov′asz, Problem5[J], Period. Math. Hung4(1974)53-62.
[44] M. Min, H.W. Du, X.H. Jia, C.X. Huang, S.C.H. Huang and W.Li. Wu, Improv-ing construction of connected dominating set with Steiner tree in wireless sonesornetworks[J]. Journal of Global Optimaization35(2006)111-119.
[45] T.N. Nguyen and D.T. Huynh, Connected d-hop dominating sets in mobile ad hocnetworks[C].4th International Symposium on Modeling and Optimization in Mobile,Ad Hoc and Wireless Networks (2006)1-8.
[46] F.G. Nocetti, J.S. Gonzalez and I. Stojmenovic, Connectivity based k-hop clusteringin wireless networks[J]. Telecommunication Systems22(2003)205-220.
[47] M.Q. Rieck, S. Pai and S. Dhar, Distributed routing algorithms for multi-hop ad hocnetworks using d-hop connected d-dominating sets[J]. Computer Networks47(2005)785-799.
[48] L. Ruan, H.W. Du, X.H. Jia, W.L. Wu, Y.S. Li and K. Ko, A greedy approximationfor minimum connected dominating sets[J]. Theoretical Computer Science329(2004)325-330.
[49] M.A. Spohn and J.J. Garcia-Luna-Aceves, Improving broadcast operations in ad hocnetworks using two-hop connected dominating sets[C]. Proc. IEEE Global Telecom-munications Conference Workshops (2004)147-152.
[50] M.A. Spohn and J.J. Garcia-Luna-Aceves, Bounded-distance multi-clusterhead for-mation in wireless ad hoc networks, Ad Hoc Networks5(2007)505-530.
[51] P. G. Tait, Remarks on colouring maps[J]. Proc. Roy. Soc. Edinburgh Ser. A10(1880)729.
[52] W. T. Tutte, On Hamilton circuits[J]. J. London Math. Soc.21(1946)98-101.
[53] P.J. Wan, K.M. Alzoubi and O. Frieder, Distributed construction of connecteddominating set in wireless ad hoc networks, Mobile Networks and Applications[M].ACM/Springer9(2002)141-149.
[54] P.J. Wan, L. Wang and F.F. Yao, Two-phased approximation algorithms for min-imum CDS in wireless ad hoc networks[C]. the28th International Conference onDistributed Computing Systems (2008)337-344.
[55] W. Wang, D. Kim, N. Sohaee, C. Ma and W. Wu, A PTAS for minimum d-hopunderwater sink placement problem in2-D underwater sensor networks[J]. DiscreteMathematics, Algorithms and Applications1(2009)283-290.
[56] G. Wegner,U¨ber endliche Kreispackungen in der Ebene[J]. Studia Sci. Math. Hungar.21(1986)1-28.
[57] W.L. Wu, H.W. Du, X.H. Jia, Y.S. Li and S.C. Huang, Minimum connected dominat-ing sets and maximal independent sets in unit disk graphs[J]. Theoretical ComputerScience352(2006)1-7.
[58] J. Wu, H. Li, On calculating connected dominating set for efcient routing in adhoc wireless networks. Proc[C].3rd ACM Int. Workshop on Discrete Algorithms andMethods for Mobile Computing and Communications1999,7-14.
[59] Z. Zhang, X.F. Gao, W.L. Wu and D.Z Du, A PTAS for minimum connected dominat-ing set in3-dimensional wireless sensor networks, Journal of Global Optimization[J].45(2009)451-458.