{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T06:18:47Z","timestamp":1725862727223},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319445427"},{"type":"electronic","value":"9783319445434"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-44543-4_19","type":"book-chapter","created":{"date-parts":[[2016,8,8]],"date-time":"2016-08-08T11:49:58Z","timestamp":1470656998000},"page":"241-252","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Upper Domination: Complexity and Approximation"],"prefix":"10.1007","author":[{"given":"Cristina","family":"Bazgan","sequence":"first","affiliation":[]},{"given":"Ljiljana","family":"Brankovic","sequence":"additional","affiliation":[]},{"given":"Katrin","family":"Casel","sequence":"additional","affiliation":[]},{"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[]},{"given":"Kim-Manuel","family":"Klein","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Lampis","sequence":"additional","affiliation":[]},{"given":"Mathieu","family":"Liedloff","sequence":"additional","affiliation":[]},{"given":"J\u00e9r\u00f4me","family":"Monnot","sequence":"additional","affiliation":[]},{"given":"Vangelis Th.","family":"Paschos","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,8,9]]},"reference":[{"key":"19_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1007\/978-3-319-12691-3_20","volume-title":"Combinatorial Optimization and Applications","author":"H AbouEisha","year":"2014","unstructured":"AbouEisha, H., Hussain, S., Lozin, V., Monnot, J., Ries, B.: A dichotomy for upper domination in monogenic classes. In: Zhang, Z., Wu, L., Xu, W., Du, D.-Z. (eds.) COCOA 2014. LNCS, vol. 8881, pp. 258\u2013267. Springer, Heidelberg (2014)"},{"issue":"1","key":"19_CR2","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0890-5401(03)00060-9","volume":"184","author":"EM Arkin","year":"2003","unstructured":"Arkin, E.M., Bender, M.A., Mitchell, J.S.B., Skiena, S.: The lazy bureaucrat scheduling problem. Inf. Comput. 184(1), 129\u2013146 (2003)","journal-title":"Inf. Comput."},{"key":"19_CR3","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, 153\u2013180 (1994)","journal-title":"J. ACM"},{"issue":"2","key":"19_CR4","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s10951-007-0038-4","volume":"11","author":"MA Bender","year":"2008","unstructured":"Bender, M.A., Clifford, R., Tsichlas, K.: Scheduling algorithms for procrastinators. J. Sched. 11(2), 95\u2013104 (2008)","journal-title":"J. Sched."},{"key":"19_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/3-540-60220-8_84","volume-title":"Algorithms and Data Structures","author":"P Berman","year":"1995","unstructured":"Berman, P., Fujito, T.: On the approximation properties of independent set problem in degree 3 graphs. In: Sack, J.-R., Akl, S.G., Dehne, F., Santoro, N. (eds.) WADS 1995. LNCS, vol. 955, pp. 449\u2013460. Springer, Heidelberg (1995)"},{"key":"19_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial \n \n \n \n $$k$$\n -arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/978-3-319-08001-7_4","volume-title":"Approximation and Online Algorithms","author":"N Boria","year":"2014","unstructured":"Boria, N., Della Croce, F.D., Paschos, V.T.: On the max min vertex cover Problem. In: Kaklamanis, C., Pruhs, K. (eds.) WAOA 2013. LNCS, vol. 8447, pp. 37\u201348. Springer, Heidelberg (2014)"},{"issue":"2","key":"19_CR8","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. Methods Softw. 10(2), 147\u2013156 (1998)","journal-title":"Optim. Methods Softw."},{"key":"19_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-642-13284-1_20","volume-title":"Structural Information and Communication Complexity","author":"N Bourgeois","year":"2010","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.T.: Fast algorithms for min independent dominating set. In: Patt-Shamir, B., Ekim, T. (eds.) SIROCCO 2010. LNCS, vol. 6058, pp. 247\u2013261. Springer, Heidelberg (2010)"},{"issue":"4\u20135","key":"19_CR10","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1016\/j.dam.2012.01.003","volume":"161","author":"N Bourgeois","year":"2013","unstructured":"Bourgeois, N., Croce, F.D., Escoffier, B., Paschos, V.T.: Fast algorithms for min independent dominating set. Discrete Appl. Math. 161(4\u20135), 558\u2013572 (2013)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"19_CR11","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0166-218X(90)90065-K","volume":"27","author":"G Cheston","year":"1990","unstructured":"Cheston, G., Fricke, G., Hedetniemi, S., Jacobs, D.: On the computational complexity of upper fractional domination. Discrete Appl. Math. 27(3), 195\u2013207 (1990)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"19_CR12","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0012-365X(81)90268-5","volume":"33","author":"EJ Cockayne","year":"1981","unstructured":"Cockayne, E.J., Favaron, O., Payan, C., Thomason, A.G.: Contributions to the theory of domination, independence and irredundance in graphs. Discrete Math. 33(3), 249\u2013258 (1981)","journal-title":"Discrete Math."},{"issue":"2","key":"19_CR13","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theo. Comp. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theo. Comp. Syst."},{"issue":"4","key":"19_CR14","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. Process. Lett. 46(4), 169\u2013172 (1993)","journal-title":"Inf. Process. Lett."},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"Hare, E.O., Hedetniemi, S.T., Laskar, R.C., Peters, K., Wimer, T.: Linear-time computability of combinatorial problems on generalized-series-parallel graphs. In: Johnson, D.S., et al. (eds.) Discrete Algorithms and Complexity (AP NY) (1987)","DOI":"10.1016\/B978-0-12-386870-1.50030-7"},{"key":"19_CR16","series-title":"Monographs and Textbooks in Pure and Applied Mathematics","volume-title":"Fundamentals of Domination in Graphs","author":"TW Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Monographs and Textbooks in Pure and Applied Mathematics, vol. 208. Marcel Dekker, New York (1998)"},{"issue":"1\u20133","key":"19_CR17","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0012-365X(96)00025-8","volume":"158","author":"MA Henning","year":"1996","unstructured":"Henning, M.A., Slater, P.J.: Inequalities relating domination parameters in cubic graphs. Discrete Math. 158(1\u20133), 87\u201398 (1996)","journal-title":"Discrete Math."},{"key":"19_CR18","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within \n \n \n \n $$n^{1-\\epsilon }$$\n . Acta Math. 182, 105\u2013142 (1999)","journal-title":"Acta Math."},{"issue":"2","key":"19_CR19","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.ipl.2008.09.021","volume":"109","author":"J Hurink","year":"2008","unstructured":"Hurink, J., Nieberg, T.: Approximating minimum independent dominating sets in wireless networks. Inf. Process. Lett. 109(2), 155\u2013160 (2008)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20133","key":"19_CR20","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0012-365X(90)90349-M","volume":"86","author":"MS Jacobson","year":"1990","unstructured":"Jacobson, M.S., Peters, K.: Chordal graphs and upper irredundance, upper domination and independence. Discrete Math. 86(1\u20133), 59\u201369 (1990)","journal-title":"Discrete Math."},{"issue":"4","key":"19_CR21","doi-asserted-by":"publisher","first-page":"1916","DOI":"10.1137\/120862612","volume":"28","author":"M Kant\u00e9","year":"2014","unstructured":"Kant\u00e9, 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":"19_CR22","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, Heidelberg (2015)"},{"key":"19_CR23","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. Discrete Appl. Math. 52, 233\u2013252 (1994)","journal-title":"Discrete Appl. Math."},{"key":"19_CR24","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0095-8956(75)90089-1","volume":"19","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: Three short proofs in graph theory. J. Combin. Theory Ser. B 19, 269\u2013271 (1975)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"3","key":"19_CR25","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"19_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/978-3-662-48054-0_49","volume-title":"Mathematical Foundations of Computer Science 2015","author":"M Zehavi","year":"2015","unstructured":"Zehavi, M.: Maximum minimal vertex cover parameterized by vertex cover. In: Italiano, G.F., Pighizzini, G., Sannella, D.T. (eds.) MFCS 2015. LNCS, vol. 9235, pp. 589\u2013600. Springer, Heidelberg (2015)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-44543-4_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T04:51:50Z","timestamp":1558327910000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-44543-4_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319445427","9783319445434"],"references-count":26,"URL":"http:\/\/dx.doi.org\/10.1007\/978-3-319-44543-4_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"9 August 2016","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":"Helsinki","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Finland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 August 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}
