{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:29Z","timestamp":1759637849605},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319080000"},{"type":"electronic","value":"9783319080017"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08001-7_4","type":"book-chapter","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T16:53:00Z","timestamp":1402419180000},"page":"37-48","source":"Crossref","is-referenced-by-count":5,"title":["On the max min vertex cover Problem"],"prefix":"10.1007","author":[{"given":"Nicolas","family":"Boria","sequence":"first","affiliation":[]},{"given":"Federico","family":"Della Croce","sequence":"additional","affiliation":[]},{"given":"Vangelis Th.","family":"Paschos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(93)90022-2","volume":"46","author":"M.M. Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson, M.M.: Approximating the minimum maximal independence number. Inform. Process. Lett.\u00a046, 169\u2013172 (1993)","journal-title":"Inform. Process. Lett."},{"key":"4_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/3-540-46632-0_7","volume-title":"Algorithms and Computations","author":"M. Damian-Iordache","year":"1999","unstructured":"Damian-Iordache, M., Pemmaraju, S.V.: Hardness of approximating independent domination in circle graphs. In: Aggarwal, A.K., Pandu Rangan, C. (eds.) ISAAC 1999. LNCS, vol.\u00a01741, pp. 56\u201369. Springer, Heidelberg (1999)"},{"key":"4_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/11917496_8","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S. Gaspers","year":"2006","unstructured":"Gaspers, S., Liedloff, M.: A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 78\u201389. Springer, Heidelberg (2006)"},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/11785293_16","volume-title":"Algorithm Theory \u2013 SWAT 2006","author":"S. Gaspers","year":"2006","unstructured":"Gaspers, S., Kratsch, D., Liedloff, M.: Exponential time algorithms for the minimum dominating set problem on some graph classes. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol.\u00a04059, pp. 148\u2013159. Springer, Heidelberg (2006)"},{"key":"4_CR5","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., Della Croce, F., Escoffier, B., Paschos, V.T.: Fast algorithms for min independent dominating set. Discrete Appl. Math.\u00a0161, 558\u2013572 (2013)","journal-title":"Discrete Appl. Math."},{"key":"4_CR6","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"4_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"Arnborg, S.: Efficient algorithms for combinatorial problems on graphs with bounded decomposability, A survey. BIT Numerical Mathematics\u00a025, 1\u201323 (1985)","journal-title":"BIT Numerical Mathematics"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Appl. Math.\u00a023, 11\u201324 (1989)","journal-title":"Discrete Appl. Math."},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/3-540-19488-6_110","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"1988","unstructured":"Bodlaender, H.L.: Dynamic programming on graphs with bounded treewidth. In: Lepist\u00f6, T., Salomaa, A. (eds.) ICALP 1988. LNCS, vol.\u00a0317, pp. 105\u2013118. Springer, Heidelberg (1988)"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/978-3-642-04128-0_51","volume-title":"Algorithms - ESA 2009","author":"J.M.M. Rooij van","year":"2009","unstructured":"van Rooij, J.M.M., Bodlaender, H.L., Rossmanith, P.: Dynamic programming on tree decompositions using generalised fast subset convolution. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 566\u2013577. Springer, Heidelberg (2009)"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Boria, N., Della Croce, F., Paschos, V.: On the max min vertex cover problem. Cahier du LAMSADE 343, LAMSADE (2013), http:\/\/www.lamsade.dauphine.fr","DOI":"10.1007\/978-3-319-08001-7_4"},{"key":"4_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/3-540-56939-1_60","volume-title":"Automata, Languages and Programming","author":"C. Lund","year":"1993","unstructured":"Lund, C., Yannakakis, M.: The approximation of maximum subgraph problems. In: Lingas, A., Carlsson, S., Karlsson, R. (eds.) ICALP 1993. LNCS, vol.\u00a0700, pp. 40\u201351. Springer, Heidelberg (1993)"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via gaussian elimination. In: Proc. FOCS 2004, pp. 248\u2013255 (2004)","DOI":"10.1007\/978-3-540-30140-0_48"},{"key":"4_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/11847250_9","volume-title":"Parameterized and Exact Computation","author":"L. Cai","year":"2006","unstructured":"Cai, L., Huang, X.: Fixed-parameter approximation: Conceptual framework and approximability results. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 96\u2013108. Springer, Heidelberg (2006)"},{"key":"4_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/11847250_10","volume-title":"Parameterized and Exact Computation","author":"Y.-J. Chen","year":"2006","unstructured":"Chen, Y.-J., Grohe, M., Gr\u00fcber, M.: On parameterized approximability. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 109\u2013120. Springer, Heidelberg (2006)"},{"key":"4_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/11847250_11","volume-title":"Parameterized and Exact Computation","author":"R.G. Downey","year":"2006","unstructured":"Downey, R.G., Fellows, M.R., McCartin, C.: Parameterized approximation problems. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol.\u00a04169, pp. 121\u2013129. Springer, Heidelberg (2006)"},{"key":"4_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-642-33293-7_5","volume-title":"Parameterized and Exact Computation","author":"B. Escoffier","year":"2012","unstructured":"Escoffier, B., Monnot, J., Paschos, V.T., Xiao, M.: New results on polynomial inapproximability and fixed parameter approximability of edge dominating set. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol.\u00a07535, pp. 25\u201336. Springer, Heidelberg (2012)"},{"key":"4_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/978-3-642-31594-7_30","volume-title":"Automata, Languages, and Programming","author":"M.R. Fellows","year":"2012","unstructured":"Fellows, M.R., Kulik, A., Rosamond, F., Shachnai, H.: Parameterized approximation via fidelity preserving transformations. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 351\u2013362. Springer, Heidelberg (2012)"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"Farber, M.: Independent domination in chordal graphs. Oper. Res. Lett.\u00a01, 134?\u2013138 (1982)","DOI":"10.1016\/0167-6377(82)90015-3"},{"key":"4_CR20","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0166-218X(84)90061-1","volume":"7","author":"M. Farber","year":"1984","unstructured":"Farber, M.: Domination, independent domination, and duality in strongly chordal graphs. Discrete Appl. Math.\u00a07, 115\u2013130 (1984)","journal-title":"Discrete Appl. Math."},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/11604686_38","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Y. Okamoto","year":"2005","unstructured":"Okamoto, Y., Uno, T., Uehara, R.: Linear-time counting algorithms for independent sets in chordal graphs. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 433\u2013444. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08001-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T12:56:04Z","timestamp":1649336164000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08001-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319080000","9783319080017"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08001-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}