{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:13Z","timestamp":1759637593092,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030174019"},{"type":"electronic","value":"9783030174026"}],"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-17402-6_11","type":"book-chapter","created":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T13:37:00Z","timestamp":1558359420000},"page":"124-136","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Extension of Vertex Cover and Independent Set in Some Classes of Graphs"],"prefix":"10.1007","author":[{"given":"Katrin","family":"Casel","sequence":"first","affiliation":[]},{"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[]},{"given":"Mehdi Khosravian","family":"Ghadikoalei","sequence":"additional","affiliation":[]},{"given":"J\u00e9r\u00f4me","family":"Monnot","sequence":"additional","affiliation":[]},{"given":"Florian","family":"Sikora","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,4,6]]},"reference":[{"key":"11_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-319-29221-2_6","volume-title":"Algorithms and Discrete Applied Mathematics","author":"C Bazgan","year":"2016","unstructured":"Bazgan, C., Brankovic, L., Casel, K., Fernau, H.: On the complexity landscape of the domination chain. In: Govindarajan, S., Maheshwari, A. (eds.) CALDAM 2016. LNCS, vol. 9602, pp. 61\u201372. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-29221-2_6"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2017.05.042","volume":"717","author":"C Bazgan","year":"2018","unstructured":"Bazgan, C., et al.: The many facets of upper domination. Theor. Comput. Sci. 717, 2\u201325 (2018)","journal-title":"Theor. Comput. Sci."},{"key":"11_CR3","unstructured":"Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness of short symmetric instances of MAX-3SAT. In: ECCC, no. 049 (2003)"},{"key":"11_CR4","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.dam.2014.06.001","volume":"196","author":"N Boria","year":"2015","unstructured":"Boria, N., Croce, F.D., Paschos, V.T.: On the max min vertex cover problem. Disc. Appl. Math. 196, 62\u201371 (2015)","journal-title":"Disc. Appl. Math."},{"issue":"2","key":"11_CR5","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1080\/10556789808805708","volume":"10","author":"E Boros","year":"1998","unstructured":"Boros, E., Gurvich, V., Hammer, P.L.: Dual subimplicants of positive Boolean functions. Optim. Meth. Softw. 10(2), 147\u2013156 (1998)","journal-title":"Optim. Meth. Softw."},{"key":"11_CR6","unstructured":"Casel, K., Fernau, H., Ghadikolaei, M.K., Monnot, J., Sikora, F.: On the complexity of solution extension of optimization problems. CoRR, abs\/1810.04553 (2018)"},{"issue":"1\u20133","key":"11_CR7","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1016\/j.dam.2003.05.004","volume":"143","author":"GJ Chang","year":"2004","unstructured":"Chang, G.J.: The weighted independent domination problem is NP-complete for chordal graphs. Disc. Appl. Math. 143(1\u20133), 351\u2013352 (2004)","journal-title":"Disc. Appl. Math."},{"issue":"6","key":"11_CR8","doi-asserted-by":"publisher","first-page":"1671","DOI":"10.1137\/S0097539792238431","volume":"27","author":"M Chang","year":"1998","unstructured":"Chang, M.: Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. Comput. 27(6), 1671\u20131694 (1998)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"11_CR9","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1137\/050646354","volume":"37","author":"J Chen","year":"2007","unstructured":"Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization: lower bounds and upper bounds on kernel size. SIAM J. Comput. 37(4), 1077\u20131106 (2007)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"11_CR10","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/0167-6377(82)90015-3","volume":"4","author":"M Farber","year":"1982","unstructured":"Farber, M.: Independent domination in chordal graphs. Oper. Res. Lett. 4(1), 134\u2013138 (1982)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"11_CR11","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(93)90022-2","volume":"46","author":"MM Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson, M.M.: Approximating the minimum maximal independence number. Inf. Proc. Lett. 46(4), 169\u2013172 (1993)","journal-title":"Inf. Proc. Lett."},{"issue":"3","key":"11_CR12","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.tcs.2005.08.031","volume":"349","author":"E Hemaspaandra","year":"2005","unstructured":"Hemaspaandra, E., Spakowski, H., Vogel, J.: The complexity of kemeny elections. Theor. Comput. Sci. 349(3), 382\u2013391 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"11_CR13","doi-asserted-by":"publisher","first-page":"1916","DOI":"10.1137\/120862612","volume":"28","author":"MM Kant\u00e9","year":"2014","unstructured":"Kant\u00e9, M.M., Limouzy, V., Mary, A., Nourine, L.: On the enumeration of minimal dominating sets and related notions. SIAM J. Disc. Math. 28(4), 1916\u20131929 (2014)","journal-title":"SIAM J. Disc. Math."},{"key":"11_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1007\/978-3-319-21840-3_37","volume-title":"Algorithms and Data Structures","author":"MM Kant\u00e9","year":"2015","unstructured":"Kant\u00e9, M.M., Limouzy, V., Mary, A., Nourine, L., Uno, T.: Polynomial delay algorithm for listing minimal edge dominating sets in graphs. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 446\u2013457. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21840-3_37"},{"key":"11_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-662-53174-7_11","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"MM Kant\u00e9","year":"2016","unstructured":"Kant\u00e9, M.M., Limouzy, V., Mary, A., Nourine, L., Uno, T.: A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs. In: Mayr, E.W. (ed.) WG 2015. LNCS, vol. 9224, pp. 138\u2013153. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53174-7_11"},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(94)90143-0","volume":"52","author":"J Kratochv\u00edl","year":"1994","unstructured":"Kratochv\u00edl, J.: A special planar satisfiability problem and a consequence of its NP-completeness. Disc. Appl. Math. 52, 233\u2013252 (1994)","journal-title":"Disc. Appl. Math."},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1137\/0209042","volume":"9","author":"EL Lawler","year":"1980","unstructured":"Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R.: Generating all maximal independent sets: NP-hardness and polynomial-time algorithms. SIAM J. Comp. 9, 558\u2013565 (1980)","journal-title":"SIAM J. Comp."},{"issue":"1\u20133","key":"11_CR18","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(98)00147-4","volume":"91","author":"DF Manlove","year":"1999","unstructured":"Manlove, D.F.: On the algorithmic complexity of twelve covering and independence parameters of graphs. Disc. Appl. Math. 91(1\u20133), 155\u2013175 (1999)","journal-title":"Disc. Appl. Math."},{"issue":"3","key":"11_CR19","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1051\/ita:2001121","volume":"35","author":"S Mishra","year":"2001","unstructured":"Mishra, S., Sikdar, K.: On the hardness of approximating some NP-optimization problems related to minimum linear ordering problem. RAIRO Inf. Th\u00e9or. Appl. 35(3), 287\u2013309 (2001)","journal-title":"RAIRO Inf. Th\u00e9or. Appl."},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: Vitter, J.S., Spirakis, P.G., Yannakakis, M. (eds.) Proceedings on 33rd Annual ACM Symposium on Theory of Computing, STOC, pp. 453\u2013461. ACM (2001)","DOI":"10.1145\/380752.380839"},{"issue":"1","key":"11_CR21","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comp. Syst. 3(1), 103\u2013128 (2007)","journal-title":"Theory Comp. Syst."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-17402-6_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T16:27:46Z","timestamp":1710347266000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-17402-6_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030174019","9783030174026"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-17402-6_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":"6 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rome","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":"27 May 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 May 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/easyconferences.eu\/ciac2019\/","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":"95","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":"32% - 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":"14","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)"}}]}}