{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T14:16:59Z","timestamp":1743085019278,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030250041"},{"type":"electronic","value":"9783030250058"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-25005-8_11","type":"book-chapter","created":{"date-parts":[[2019,7,14]],"date-time":"2019-07-14T23:02:23Z","timestamp":1563145343000},"page":"122-135","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Power Edge Set and Zero Forcing Set Remain Difficult in Cubic Graphs"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Cazals","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benoit","family":"Darties","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Annie","family":"Chateau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodolphe","family":"Giroudeau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathias","family":"Weller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,10]]},"reference":[{"issue":"1","key":"11_CR1","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B Baker","year":"1994","unstructured":"Baker, B.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"11_CR2","unstructured":"Bar-Yehuda, R., Even, S.: On approximating a vertex cover for planar graphs. In: Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 5\u20137 May 1982, San Francisco, California, USA, pp. 303\u2013309 (1982)"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"1628","DOI":"10.1016\/j.laa.2007.10.009","volume":"428","author":"F Barioli","year":"2008","unstructured":"Barioli, F., et al.: Zero forcing sets and the minimum rank of graphs. Linear Algebra Appl. 428, 1628\u20131648 (2008)","journal-title":"Linear Algebra Appl."},{"issue":"4","key":"11_CR4","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.: A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. Networks 42(4), 202\u2013208 (2003)","journal-title":"Networks"},{"key":"11_CR5","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.jda.2018.11.006","volume":"52\u201353","author":"B Darties","year":"2018","unstructured":"Darties, B., Champseix, N., Chateau, A., Giroudeau, R., Weller, M.: Complexity and lowers bounds for power edge set problem. J. Discrete Algorithms 52\u201353, 70\u201391 (2018)","journal-title":"J. Discrete Algorithms"},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162, 439\u2013485 (2005)","journal-title":"Ann. Math."},{"issue":"6","key":"11_CR7","doi-asserted-by":"publisher","first-page":"1023","DOI":"10.1016\/j.dam.2005.08.006","volume":"154","author":"M Dorfling","year":"2006","unstructured":"Dorfling, M., Henning, M.A.: A note on power domination in grid graphs. Discrete Appl. Math. 154(6), 1023\u20131027 (2006)","journal-title":"Discrete Appl. Math."},{"key":"11_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-3-642-31770-5_33","volume-title":"Combinatorial Optimization and Applications","author":"N Fan","year":"2012","unstructured":"Fan, N., Watson, J.-P.: Solving the connected dominating set problem and power dominating set problem by integer programming. In: Lin, G. (ed.) COCOA 2012. LNCS, vol. 7402, pp. 371\u2013383. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31770-5_33"},{"key":"11_CR9","unstructured":"Feige, U.: Vertex cover is hardest to approximate on regular graphs. Technical Report MCS03-15 (2003)"},{"issue":"3","key":"11_CR10","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"DR Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pac. J. Math. 15(3), 835\u2013855 (1965). https:\/\/projecteuclid.org:443\/euclid.pjm\/1102995572","journal-title":"Pac. J. Math."},{"key":"11_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR 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":"3","key":"11_CR12","doi-asserted-by":"publisher","first-page":"1099","DOI":"10.1109\/TPWRS.2008.926475","volume":"23","author":"B Gou","year":"2008","unstructured":"Gou, B.: Generalized integer linear programming formulation for optimal PMU placement. IEEE Trans. Power Syst. 23(3), 1099\u20131104 (2008)","journal-title":"IEEE Trans. Power Syst."},{"issue":"2","key":"11_CR13","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s00453-007-9147-x","volume":"52","author":"J Guo","year":"2008","unstructured":"Guo, J., Niedermeier, R., Raible, D.: Improved algorithms and complexity results for power domination in graphs. Algorithmica 52(2), 177\u2013202 (2008)","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"11_CR14","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M Habib","year":"2000","unstructured":"Habib, M., McConnell, R.M., Paul, C., Viennot, L.: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci. 234(1\u20132), 59\u201384 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"11_CR15","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1137\/S0895480100375831","volume":"15","author":"TW 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. Discrete Math. 15(4), 519\u2013529 (2002)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"11_CR16","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2- $$\\varepsilon $$. J. Comput. Syst. Sci. 74(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"8","key":"11_CR17","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., Wan, P., Du, D.: On greedy construction of connected dominating sets in wireless networks. Wirel. Commun. Mobile Comput. 5(8), 927\u2013932 (2005)","journal-title":"Wirel. Commun. Mobile Comput."},{"issue":"5","key":"11_CR18","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. ACM (JACM) 41(5), 960\u2013981 (1994)","journal-title":"J. ACM (JACM)"},{"issue":"12","key":"11_CR19","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1109\/MPER.2002.4311912","volume":"22","author":"B Milosevic","year":"2002","unstructured":"Milosevic, B., Begovic, M.: Nondominated sorting genetic algorithm for optimal phasor maesurement placement. IEEE Power Eng. Rev. 22(12), 61\u201361 (2002)","journal-title":"IEEE Power Eng. Rev."},{"issue":"2","key":"11_CR20","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1002\/net.21684","volume":"68","author":"P Poirion","year":"2016","unstructured":"Poirion, P., Toubaline, S., D\u2019Ambrosio, C., Liberti, L.: The power edge set problem. Networks 68(2), 104\u2013120 (2016)","journal-title":"Networks"},{"key":"11_CR21","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., Salles da Cunha, A., 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. 6701, pp. 162\u2013169. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-21527-8_21"},{"issue":"3","key":"11_CR22","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1109\/LCOMM.2006.1603363","volume":"10","author":"MT Thai","year":"2006","unstructured":"Thai, M.T., Du, D.Z.: Connected dominating sets in disk graphs with bidirectional links. IEEE Commun. Lett. 10(3), 138\u2013140 (2006)","journal-title":"IEEE Commun. Lett."},{"issue":"3","key":"11_CR23","doi-asserted-by":"publisher","first-page":"895","DOI":"10.1007\/s10878-017-0241-y","volume":"35","author":"S Toubaline","year":"2018","unstructured":"Toubaline, S., D\u2019Ambrosio, C., Liberti, L., Poirion, P., Schieber, B., Shachnai, H.: Complexity and inapproximability results for the power edge set problem. J. Comb. Optim. 35(3), 895\u2013905 (2018)","journal-title":"J. Comb. Optim."},{"key":"11_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-319-26626-8_27","volume-title":"Combinatorial Optimization and Applications","author":"S Toubaline","year":"2015","unstructured":"Toubaline, S., Poirion, P.-L., D\u2019Ambrosio, C., Liberti, L.: Observing the state of a smart grid using bilevel programming. In: Lu, Z., Kim, D., Wu, W., Li, W., Du, D.-Z. (eds.) COCOA 2015. LNCS, vol. 9486, pp. 364\u2013376. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-26626-8_27"},{"key":"11_CR25","doi-asserted-by":"crossref","unstructured":"Yuill, W., Edwards, A., Chowdhury, S., Chowdhury, S.P.: Optimal PMU placement: a comprehensive literature review. In: 2011 IEEE Power and Energy Society General Meeting, July, pp. 1\u20138 (2011)","DOI":"10.1109\/PES.2011.6039376"}],"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-25005-8_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T17:13:09Z","timestamp":1710349989000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-25005-8_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030250041","9783030250058"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-25005-8_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"10 July 2019","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":"Pisa","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/iwoca2019.di.unipi.it\/","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":"73","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":"36","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":"49% - 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","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-6","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":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}