{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T10:33:39Z","timestamp":1742985219706,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030489656"},{"type":"electronic","value":"9783030489663"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-48966-3_28","type":"book-chapter","created":{"date-parts":[[2020,5,28]],"date-time":"2020-05-28T13:04:23Z","timestamp":1590671063000},"page":"368-381","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination"],"prefix":"10.1007","author":[{"given":"Ioannis","family":"Lamprou","sequence":"first","affiliation":[]},{"given":"Ioannis","family":"Sigalas","sequence":"additional","affiliation":[]},{"given":"Vassilis","family":"Zissimopoulos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,5,29]]},"reference":[{"key":"28_CR1","unstructured":"Arora, S., Lund, C.: Hardness of approximations. In: Approximation Algorithms for NP-Hard Problems, chap. 10, pp. 399\u2013446. PWS Publishing Co., Boston (1997)"},{"key":"28_CR2","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s00010-015-0354-2","volume":"90","author":"R Boutrig","year":"2016","unstructured":"Boutrig, R., Chellali, M., Haynes, T.W., Hedetniemi, S.T.: Vertex-edge domination in graphs. Aequat. Math. 90, 355\u2013366 (2016). https:\/\/doi.org\/10.1007\/s00010-015-0354-2","journal-title":"Aequat. Math."},{"key":"28_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-319-51741-4_4","volume-title":"Approximation and Online Algorithms","author":"J-C Bermond","year":"2017","unstructured":"Bermond, J.-C., et al.: Bin packing with colocations. In: Jansen, K., Mastrolilli, M. (eds.) WAOA 2016. LNCS, vol. 10138, pp. 40\u201351. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-51741-4_4"},{"key":"28_CR4","series-title":"Springer Optimization and its Applications","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-5242-3","volume-title":"Connected Dominating Set: Theory and Applications","author":"DZ Du","year":"2013","unstructured":"Du, D.Z., Wan, P.J.: Connected Dominating Set: Theory and Applications. Springer Optimization and its Applications. Springer, New York (2013). https:\/\/doi.org\/10.1007\/978-1-4614-5242-3"},{"issue":"4","key":"28_CR5","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"28_CR6","doi-asserted-by":"crossref","unstructured":"Garg, N.: Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing (STOC), pp. 396\u2013402 (2005)","DOI":"10.1145\/1060590.1060650"},{"issue":"4","key":"28_CR7","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/PL00009201","volume":"20","author":"S Guha","year":"1998","unstructured":"Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20(4), 374\u2013387 (1998)","journal-title":"Algorithmica"},{"issue":"3","key":"28_CR8","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1137\/0406030","volume":"6","author":"JD Horton","year":"1993","unstructured":"Horton, J.D., Kilakos, K.: Minimum edge dominating sets. SIAM J. Discrete Math. 6(3), 375\u2013387 (1993)","journal-title":"SIAM J. Discrete Math."},{"key":"28_CR9","unstructured":"Johnson, D.S., Minkoff, M., Phillips, S.: The prize collecting Steiner tree problem: theory and practice. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete algorithms (SODA), pp. 760\u2013769 (2000)"},{"key":"28_CR10","doi-asserted-by":"publisher","first-page":"2380","DOI":"10.3390\/en11092380","volume":"11","author":"NM Khoa","year":"2018","unstructured":"Khoa, N.M., Tung, D.D.: Locating fault on transmission line with static var compensator based on phasor measurement unit. Energies 11, 2380 (2018)","journal-title":"Energies"},{"issue":"1","key":"28_CR11","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S Khuller","year":"1999","unstructured":"Khuller, S., Moss, A., Naor, J.S.: The budgeted maximum coverage problem. Inf. Process. Lett. 70(1), 39\u201345 (1999)","journal-title":"Inf. Process. Lett."},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"Khuller, S., Purohit, M., Sarpatwar, K.K.: Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1702\u20131713 (2014)","DOI":"10.1137\/1.9781611973402.123"},{"issue":"1","key":"28_CR13","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1137\/18M1212094","volume":"34","author":"S Khuller","year":"2020","unstructured":"Khuller, S., Purohit, M., Sarpatwar, K.K.: Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems. SIAM J. Discrete Math. 34(1), 251\u2013270 (2020)","journal-title":"SIAM J. Discrete Math."},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"Kumar, R., Kaur, J.: Efficient beacon placement for network tomography. In: Proceedings of the 4th ACM SIGCOMM Conference on Internet Measurement, pp. 181\u2013186 (2004)","DOI":"10.1145\/1028788.1028810"},{"key":"28_CR15","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.tcs.2018.09.008","volume":"794","author":"I Lamprou","year":"2018","unstructured":"Lamprou, I., Martin, R., Schewe, S.: Eternally dominating large grids. Theoret. Comput. Sci. 794, 27\u201346 (2018)","journal-title":"Theoret. Comput. Sci."},{"key":"28_CR16","unstructured":"Lamprou, I., Martin, R., Schewe, S., Sigalas, I., Zissimopoulos, V.: Maximum rooted connected expansion. In: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), LIPIcs, vol. 117, pp. 25:1\u201325:14 (2018)"},{"key":"28_CR17","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.tcs.2012.11.035","volume":"476","author":"JK Lan","year":"2013","unstructured":"Lan, J.K., Chang, G.J.: On the mixed domination problem in graphs. Theoret. Comput. Sci. 476, 84\u201393 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"28_CR18","unstructured":"Lewis, J.: Vertex-edge and edge-vertex parameters in graphs. All Dissertations, 103 (2007)"},{"key":"28_CR19","unstructured":"Liu, Y., Liang, W.: Approximate coverage in wireless sensor networks. In: The IEEE Conference on Local Computer Networks 30th Anniversary (LCN 2005), pp. 68\u201375 (2005)"},{"issue":"2","key":"28_CR20","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/s11276-015-0981-5","volume":"22","author":"X Liu","year":"2015","unstructured":"Liu, X., Wang, W., Kim, D., Yang, Z., Tokuta, A., Jiang, Y.: The first constant factor approximation for minimum partial connected dominating set problem in growth-bounded graphs. Wirel. Netw. 22(2), 553\u2013562 (2015). https:\/\/doi.org\/10.1007\/s11276-015-0981-5","journal-title":"Wirel. Netw."},{"key":"28_CR21","unstructured":"Miyano, E., Ono, H.: Maximum domination problem. In: Proceedings of the Seventeenth Computing: the Australasian Theory Symposium (CATS), vol. 119, pp. 55\u201362 (2011)"},{"key":"28_CR22","unstructured":"Peters, K.W.: Theoretical and algorithmic results on domination and connectivity. Ph.D. thesis, Clemson University, Clemson (1986)"},{"key":"28_CR23","first-page":"399","volume":"54","author":"E Sampathkumar","year":"1992","unstructured":"Sampathkumar, E., Kamath, S.S.: Mixed domination in graphs. Sankhya Indian J. Stat. 54, 399\u2013402 (1992)","journal-title":"Sankhya Indian J. Stat."},{"key":"28_CR24","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0020-0190(97)00182-8","volume":"64","author":"P Slav\u00edk","year":"1997","unstructured":"Slav\u00edk, P.: Improved performance of the greedy algorithm for partial cover. Inf. Process. Lett. 64, 251\u2013254 (1997)","journal-title":"Inf. Process. Lett."},{"key":"28_CR25","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.ipl.2018.01.012","volume":"134","author":"YB Venkatakrishnan","year":"2018","unstructured":"Venkatakrishnan, Y.B., Krishnakumari, B.: An improved upper bound of edge-vertex domination number of a tree. Inf. Process. Lett. 134, 14\u201317 (2018)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"28_CR26","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/1978802.1978811","volume":"43","author":"B Wang","year":"2011","unstructured":"Wang, B.: Coverage problems in sensor networks. ACM Comput. Surv. 43(4), 32 (2011)","journal-title":"ACM Comput. Surv."},{"issue":"3","key":"28_CR27","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M Yannakakis","year":"1980","unstructured":"Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38(3), 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."},{"key":"28_CR28","doi-asserted-by":"publisher","first-page":"2387","DOI":"10.1016\/j.tcs.2011.01.029","volume":"412","author":"Y Zhao","year":"2011","unstructured":"Zhao, Y., Kang, L., Sohn, M.Y.: The algorithmic complexity of mixed domination in graphs. Theoret. Comput. Sci. 412, 2387\u20132392 (2011)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-48966-3_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T15:17:31Z","timestamp":1710256651000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-48966-3_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030489656","9783030489663"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-48966-3_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"29 May 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Bordeaux","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 June 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 June 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2020.labri.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"62","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"48% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3,8","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5,9","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference had to be postponed due to the COVID-19 pandemic","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}