{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:39:14Z","timestamp":1725795554211},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319080000"},{"type":"electronic","value":"9783319080017"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08001-7_7","type":"book-chapter","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T12:53:00Z","timestamp":1402404780000},"page":"73-84","source":"Crossref","is-referenced-by-count":2,"title":["Approximating the Sparsest k-Subgraph in Chordal Graphs"],"prefix":"10.1007","author":[{"given":"R\u00e9mi","family":"Watrigant","sequence":"first","affiliation":[]},{"given":"Marin","family":"Bougeret","sequence":"additional","affiliation":[]},{"given":"Rodolphe","family":"Giroudeau","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"7_CR1","doi-asserted-by":"publisher","first-page":"1297","DOI":"10.1137\/060651136","volume":"23","author":"N. Apollonio","year":"2009","unstructured":"Apollonio, N., Seb\u0151, A.: Minconvex factors of prescribed size in graphs. SIAM Journal of Discrete Mathematics\u00a023(3), 1297\u20131310 (2009)","journal-title":"SIAM Journal of Discrete Mathematics"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Apollonio, N., Simeone, B.: The maximum vertex coverage problem on bipartite graphs. Preprint (2013)","DOI":"10.1016\/j.dam.2013.05.015"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: An \n                  \n                    \n                  \n                  $\\mathcal{O}(n^{1\/4})$\n                 approximation for densest k-subgraph. In: Proceedings of the 42nd ACM symposium on Theory of Computing, pp. 201\u2013210. ACM (2010)","DOI":"10.1145\/1806689.1806719"},{"issue":"1","key":"7_CR4","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s10878-010-9343-5","volume":"23","author":"N. Bourgeois","year":"2012","unstructured":"Bourgeois, N., Giannakos, A., Lucarelli, G., Milis, I., Paschos, V., Potti\u00e9, O.: The max quasi-independent set problem. Journal of Combinatorial Optimization\u00a023(1), 94\u2013117 (2012)","journal-title":"Journal of Combinatorial Optimization"},{"key":"7_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-642-28050-4_17","volume-title":"Parameterized and Exact Computation","author":"H. Broersma","year":"2012","unstructured":"Broersma, H., Golovach, P.A., Patel, V.: Tight complexity bounds for FPT subgraph problems parameterized by clique-width. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol.\u00a07112, pp. 207\u2013218. Springer, Heidelberg (2012)"},{"key":"7_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/BFb0028569","volume-title":"STACS 98","author":"N. Bshouty","year":"1998","unstructured":"Bshouty, N., Burroughs, L.: Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. In: Meinel, C., Morvan, M., Krob, D. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 298\u2013308. Springer, Heidelberg (1998)"},{"issue":"1","key":"7_CR7","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1093\/comjnl\/bxm086","volume":"51","author":"L. Cai","year":"2008","unstructured":"Cai, L.: Parameterized complexity of cardinality constrained optimization problems. Computer Journal\u00a051(1), 102\u2013121 (2008)","journal-title":"Computer Journal"},{"issue":"1","key":"7_CR8","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0166-218X(84)90088-X","volume":"9","author":"D.G. Corneil","year":"1984","unstructured":"Corneil, D.G., Perl, Y.: Clustering and domination in perfect graphs. Discrete Applied Mathematics\u00a09(1), 27\u201339 (1984)","journal-title":"Discrete Applied Mathematics"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D. Fulkerson","year":"1965","unstructured":"Fulkerson, D., Gross, O.: Incidence matrices and interval graphs. Pacific J. Math.\u00a015, 835\u2013855 (1965)","journal-title":"Pacific J. Math."},{"issue":"2","key":"7_CR10","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0166-218X(96)00030-3","volume":"74","author":"O. Goldschmidt","year":"1997","unstructured":"Goldschmidt, O., Hochbaum, D.S.: k-edge subgraph problems. Discrete Applied Mathematics\u00a074(2), 159\u2013169 (1997)","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"7_CR11","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s00224-007-1309-3","volume":"41","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of vertex cover variants. Theory of Computing Systems\u00a041(3), 501\u2013520 (2007)","journal-title":"Theory of Computing Systems"},{"key":"7_CR12","unstructured":"Joret, G., Vetta, A.: Reducing the rank of a matroid. CoRR, abs\/1211.4853 (2012)"},{"key":"7_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-540-92248-3_22","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J. Kneis","year":"2008","unstructured":"Kneis, J., Langer, A., Rossmanith, P.: Improved upper bounds for partial vertex cover. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol.\u00a05344, pp. 240\u2013251. Springer, Heidelberg (2008)"},{"issue":"1","key":"7_CR14","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/j.ipl.2008.03.016","volume":"108","author":"M. Liazi","year":"2008","unstructured":"Liazi, M., Milis, I., Zissimopoulos, V.: A constant approximation algorithm for the densest k-subgraph problem on chordal graphs. Information Processing Letters\u00a0108(1), 29\u201332 (2008)","journal-title":"Information Processing Letters"},{"key":"7_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1007\/978-3-642-22300-6_53","volume-title":"Algorithms and Data Structures","author":"T. Nonner","year":"2011","unstructured":"Nonner, T.: PTAS for densest k-subgraph in interval graphs. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol.\u00a06844, pp. 631\u2013641. Springer, Heidelberg (2011)"},{"key":"7_CR16","unstructured":"Watrigant, R., Bougeret, M., Giroudeau, R.: The k-sparsest subgraph problem. Technical Report RR-12019, LIRMM (2012)"},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"Watrigant, R., Bougeret, M., Giroudeau, R.: Approximating the sparsest k-subgraph in chordal graphs. Technical Report hal-00868188, LIRMM (2013)","DOI":"10.1007\/978-3-319-08001-7_7"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08001-7_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T21:30:59Z","timestamp":1558906259000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08001-7_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319080000","9783319080017"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08001-7_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}