{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,7]],"date-time":"2025-05-07T10:14:34Z","timestamp":1746612874299},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642317699"},{"type":"electronic","value":"9783642317705"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31770-5_33","type":"book-chapter","created":{"date-parts":[[2012,7,26]],"date-time":"2012-07-26T05:03:12Z","timestamp":1343278992000},"page":"371-383","source":"Crossref","is-referenced-by-count":34,"title":["Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming"],"prefix":"10.1007","author":[{"given":"Neng","family":"Fan","sequence":"first","affiliation":[]},{"given":"Jean-Paul","family":"Watson","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"33_CR1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"issue":"4","key":"33_CR2","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1002\/net.10097","volume":"42","author":"X. Cheng","year":"2003","unstructured":"Cheng, X., Huang, X., Li, D., Wu, W., Du, D.-Z.: A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks\u00a042(4), 202\u2013208 (2003)","journal-title":"Networks"},{"key":"33_CR3","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1002\/wcm.356","volume":"5","author":"Y. Li","year":"2005","unstructured":"Li, Y., Thai, M.T., Wang, F., Yi, C.W., Wan, P.J., Du, D.-Z.: On greedy construction of connected dominating sets in wireless networks. Wirel. Commun. Mob. Comp.\u00a05, 927\u2013932 (2005)","journal-title":"Wirel. Commun. Mob. Comp."},{"issue":"4","key":"33_CR4","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1007\/s10898-009-9511-2","volume":"48","author":"X. Zhu","year":"2010","unstructured":"Zhu, X., Yu, J., Lee, W., Kim, D., Shan, S., Du, D.-Z.: New dominating sets in social networks. J. Global Optim.\u00a048(4), 633\u2013642 (2010)","journal-title":"J. Global Optim."},{"issue":"3","key":"33_CR5","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s11590-009-0151-8","volume":"4","author":"W. Wu","year":"2010","unstructured":"Wu, W., Gao, X., Pardalos, P.M., Du, D.-Z.: Wireless networking, dominating and packing. Optim. Lett.\u00a04(3), 347\u2013358 (2010)","journal-title":"Optim. Lett."},{"issue":"2","key":"33_CR6","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s11590-010-0208-8","volume":"5","author":"L. Ding","year":"2011","unstructured":"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.\u00a05(2), 297\u2013306 (2011)","journal-title":"Optim. Lett."},{"issue":"3","key":"33_CR7","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1109\/LCOMM.2006.1603363","volume":"10","author":"M.T. Thai","year":"2006","unstructured":"Thai, M.T., Du, D.-Z.: Connected dominating sets in disk graphs with bidirectional links. IEEE Commun. Lett.\u00a010(3), 138\u2013140 (2006)","journal-title":"IEEE Commun. Lett."},{"issue":"8","key":"33_CR8","doi-asserted-by":"publisher","first-page":"1108","DOI":"10.1109\/TMC.2010.55","volume":"9","author":"D. Kim","year":"2010","unstructured":"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. Mob. Comp.\u00a09(8), 1108\u20131118 (2010)","journal-title":"IEEE Trans. Mob. Comp."},{"key":"33_CR9","doi-asserted-by":"crossref","unstructured":"Blum, J., Ding, M., Thaeler, A., Cheng, X.: Connected dominating set in sensor networks and MANET. In: Du, D.-Z., Pardalos, P. (eds.) Handbook of Combinatorial Optimization, pp. 329\u2013369 (2004)","DOI":"10.1007\/0-387-23830-1_8"},{"key":"33_CR10","doi-asserted-by":"publisher","first-page":"1081","DOI":"10.3923\/itj.2010.1081.1092","volume":"9","author":"Z. Liu","year":"2010","unstructured":"Liu, Z., Wang, B., Guo, L.: A Survey on connected dominating set construction algorithm for wireless sensor networks. Informa. Technol. J.\u00a09, 1081\u20131092 (2010)","journal-title":"Informa. Technol. J."},{"key":"33_CR11","doi-asserted-by":"crossref","unstructured":"Mnif, K., Rong, B., Kadoch, M.: Virtual backbone based on mcds for topology control in wireless ad hoc networks. In: Proceedings of the 2nd ACM International Workshop on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks, Quebec, Canada (2005)","DOI":"10.1145\/1089803.1089991"},{"key":"33_CR12","doi-asserted-by":"crossref","unstructured":"Yuan, D.: Energy-efficient broadcasting in wireless ad hoc networks: performance benchmarking and distributed algorithms based on network connectivity characterization. In: Proceedings of MSWiM, Quebec, Canada (2005)","DOI":"10.1145\/1089444.1089451"},{"key":"33_CR13","unstructured":"Morgan, M.J., Grout, V.: Finding optimal solutions to backbone minimisation problems using mixed integer programming. In: Proceedings of the Seventh International Network Conference (INC 2008), Boston, MA, pp. 53\u201363 (2008)"},{"key":"33_CR14","doi-asserted-by":"crossref","unstructured":"Wightman, P.M., Fabregasy, A., Labradorz, M.A.: An optimal solution to the MCDS problem for topology construction in wireless sensor networks. In: 2010 IEEE Latin-American Conference on Communications (LATINCOM), Belem, Brazil (2010)","DOI":"10.1109\/LATINCOM.2010.5641018"},{"key":"33_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/978-3-642-21527-8_21","volume-title":"Network Optimization","author":"L. Simonetti","year":"2011","unstructured":"Simonetti, L., da Cunha, A.S., Lucena, A.: The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm. In: Pahl, J., Reiners, T., Vo\u00df, S. (eds.) INOC 2011. LNCS, vol.\u00a06701, pp. 162\u2013169. Springer, Heidelberg (2011)"},{"issue":"1","key":"33_CR16","first-page":"104","volume":"25","author":"P.C. Pop","year":"2009","unstructured":"Pop, P.C.: A survey of different integer programming formulations of the generalized minimum spanning tree problem. Carpathian J. Mathematics\u00a025(1), 104\u2013118 (2009)","journal-title":"Carpathian J. Mathematics"},{"key":"33_CR17","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1137\/S0895480100375831","volume":"15","author":"T.W. Haynes","year":"2002","unstructured":"Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Henning, M.A.: Domination in graphs applied to electric power networks. SIAM J. Disc. Math.\u00a015, 519\u2013529 (2002)","journal-title":"SIAM J. Disc. Math."},{"key":"33_CR18","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1109\/TPWRS.2009.2036470","volume":"25","author":"F. Aminifar","year":"2010","unstructured":"Aminifar, F., Khodaei, A., Fotuhi-Firuzabad, M., Shahidehpour, M.: Contingency-constrained PMU placement in power networks. IEEE Trans. Power Syst.\u00a025, 516\u2013523 (2010)","journal-title":"IEEE Trans. Power Syst."},{"key":"33_CR19","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s10878-008-9176-7","volume":"19","author":"A. Aazami","year":"2010","unstructured":"Aazami, A.: Domination in graphs with bounded progagation: algorithms, formulations and hardness results. J. Comb. Optim.\u00a019, 429\u2013456 (2010)","journal-title":"J. Comb. Optim."},{"key":"33_CR20","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1145\/321043.321046","volume":"7","author":"C.E. Miller","year":"1960","unstructured":"Miller, C.E., Tucker, A.W., Zemlin, R.A.: Integer programming formulation of traveling salesman problems. J. Assoc. Comp. Mach.\u00a07, 326\u2013329 (1960)","journal-title":"J. Assoc. Comp. Mach."},{"key":"33_CR21","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1016\/j.dam.2009.01.017","volume":"158","author":"F.R. Quintao","year":"2010","unstructured":"Quintao, F.R., da Cunha, A.S., Mateus, G.R., Lucena, A.: The k-cardinality tree problem: reformulations and lagrangian relaxation. Disc. Appl. Math.\u00a0158, 1305\u20131314 (2010)","journal-title":"Disc. Appl. Math."},{"key":"33_CR22","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0167-6377(91)90083-2","volume":"10","author":"M. Desrochers","year":"1991","unstructured":"Desrochers, M., Gilbert, L.: Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints. Oper. Res. Lett.\u00a010, 27\u201336 (1991)","journal-title":"Oper. Res. Lett."},{"key":"33_CR23","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0167-6377(91)90028-N","volume":"10","author":"R.K. Martin","year":"1991","unstructured":"Martin, R.K.: Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett.\u00a010, 119\u2013128 (1991)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"33_CR24","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/0022-0000(91)90024-Y","volume":"43","author":"M. Yannakakis","year":"1991","unstructured":"Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comp. Syst. Sci.\u00a043(3), 441\u2013466 (1991)","journal-title":"J. Comp. Syst. Sci."},{"key":"33_CR25","doi-asserted-by":"crossref","unstructured":"Conforti, M., Cornu\u00e9jols, G., Zambelli, G.: Extended formulations in combinatorial optimization. 4OR\u00a0(8), 1\u201348 (2010)","DOI":"10.1007\/s10288-010-0122-z"},{"key":"33_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-642-13036-6_11","volume-title":"Integer Programming and Combinatorial Optimization","author":"V. Kaibel","year":"2010","unstructured":"Kaibel, V., Pashkovich, K., Theis, D.O.: Symmetry Matters for the Sizes of Extended Formulations. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol.\u00a06080, pp. 135\u2013148. Springer, Heidelberg (2010)"},{"key":"33_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/978-3-642-13520-0_14","volume-title":"Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems","author":"B. Dilkina","year":"2010","unstructured":"Dilkina, B., Gomes, C.P.: Solving Connected Subgraph Problems in Wildlife Conservation. In: Lodi, A., Milano, M., Toth, P. (eds.) CPAIOR 2010. LNCS, vol.\u00a06140, pp. 102\u2013116. Springer, Heidelberg (2010)"},{"key":"33_CR28","unstructured":"IEEE reliability test data (2012), http:\/\/www.ee.washington.edu\/research\/pstca\/"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31770-5_33.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:08:59Z","timestamp":1606187339000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31770-5_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642317699","9783642317705"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31770-5_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}