{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,20]],"date-time":"2024-05-20T09:55:28Z","timestamp":1716198928168},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,9,13]],"date-time":"2014-09-13T00:00:00Z","timestamp":1410566400000},"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":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00224-014-9568-2","type":"journal-article","created":{"date-parts":[[2015,4,29]],"date-time":"2015-04-29T12:25:21Z","timestamp":1430310321000},"page":"111-132","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Approximating the Sparsest k-Subgraph in Chordal Graphs"],"prefix":"10.1007","volume":"58","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","published-online":{"date-parts":[[2014,9,13]]},"reference":[{"issue":"3","key":"9568_CR1","doi-asserted-by":"crossref","first-page":"1297","DOI":"10.1137\/060651136","volume":"23","author":"N Apollonio","year":"2009","unstructured":"Apollonio, N., Sebo\u030b, A.: Minconvex Factors of Prescribed Size in Graphs. SIAM J. Discret. Math. 23(3), 1297\u20131310 (2009)","journal-title":"SIAM J. Discret. Math."},{"key":"9568_CR2","doi-asserted-by":"crossref","unstructured":"Apollonio, N., Simeone, B.: The Maximum Vertex Coverage Problem on Bipartite Graphs. in press (2013)","DOI":"10.1016\/j.dam.2013.05.015"},{"key":"9568_CR3","unstructured":"Brandsta\u030bd, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Soc. Ind. Appl. Math. (1987)"},{"key":"9568_CR4","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting High Log-Densities: an \ud835\udcde ( n 1 \/ 4 ) $\\mathcal {O}(n^{1\/4})$ Approximation for Densest k-Subgraph. In: Proceedings of the 42nd ACM symposium on Theory of Computing, pp. 201\u2013210 (2010)","DOI":"10.1145\/1806689.1806719"},{"issue":"1","key":"9568_CR5","doi-asserted-by":"crossref","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.Th., Potti\u00e9, O.: The Max Quasi-Independent Set Problem. J. Comb. Optim. 23(1), 94\u2013117 (2012)","journal-title":"J. Comb. Optim."},{"key":"9568_CR6","doi-asserted-by":"crossref","unstructured":"Broersma, H., Golovach, P.A., Patel, V.: Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width. In: Proceedings of the 6th international conference on Parameterized and Exact Computation, pp. 207\u2013218 (2012)","DOI":"10.1007\/978-3-642-28050-4_17"},{"key":"9568_CR7","doi-asserted-by":"crossref","unstructured":"Bshouty, N., Burroughs, L.: Massaging a Linear Programming Solution to Give a 2-Approximation for a Generalization of the Vertex Cover Problem. In: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science, pp. 298\u2013308 (1998)","DOI":"10.1007\/BFb0028569"},{"issue":"1","key":"9568_CR8","first-page":"102","volume":"51","author":"Leizhen Cai","year":"2008","unstructured":"Leizhen Cai.: Parameterized Complexity of Cardinality Constrained Optimization Problems. Comput. J. 51(1), 102\u2013121 (2008)","journal-title":"Comput. J."},{"key":"9568_CR9","doi-asserted-by":"crossref","unstructured":"Chen, D., Fleischer, R., Li, J.: Densest k-Subgraph Approximation on Intersection Graphs. In: Proceedings of the 8th international Conference on Approximation and Online Algorithms, pp. 83\u201393 (2011)","DOI":"10.1007\/978-3-642-18318-8_8"},{"issue":"1","key":"9568_CR10","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0166-218X(84)90088-X","volume":"9","author":"DG Corneil","year":"1984","unstructured":"Corneil, D.G., Perl, Y.: Clustering and Domination in Perfect Graphs. Discret. Appl. Math. 9(1), 27\u201339 (1984)","journal-title":"Discret. Appl. Math."},{"key":"9568_CR11","doi-asserted-by":"crossref","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. Pac. J. Math. 15, 835\u2013855 (1965)","journal-title":"Pac. J. Math."},{"issue":"2","key":"9568_CR12","doi-asserted-by":"crossref","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. Discret. Appl. Math. 74(2), 159\u2013169 (1997)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"9568_CR13","doi-asserted-by":"crossref","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 Comput. Syst. 41(3), 501\u2013520 (2007)","journal-title":"Theory Comput. Syst."},{"key":"9568_CR14","unstructured":"Joret, G., Vetta, A.: Reducing the rank of a matroid, CoRR. arXiv: 1211.4853 (2012)"},{"key":"9568_CR15","doi-asserted-by":"crossref","unstructured":"Kneis, J., Langer, A., Rossmanith, P.: Improved Upper Bounds for Partial Vertex Cover. In: Proceedings of the 34th Workshop of Graph Theoretic Concepts in Computer Science, pp. 240\u2013251 (2008)","DOI":"10.1007\/978-3-540-92248-3_22"},{"issue":"1","key":"9568_CR16","doi-asserted-by":"crossref","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. Inf. Process. Lett. 108(1), 29\u201332 (2008)","journal-title":"Inf. Process. Lett."},{"key":"9568_CR17","doi-asserted-by":"crossref","unstructured":"Nonner, T.: PTAS for Densest k-Subgraph in Interval Graphs. In: Proceedings of the 12th International Conference on Algorithms and Data Structures, pp. 631\u2013641 (2011)","DOI":"10.1007\/978-3-642-22300-6_53"},{"key":"9568_CR18","unstructured":"Watrigant, R., Bougeret, M., Giroudeau, R.: The k-Sparsest Subgraph Problem, Technical Report RR-12019. LIRMM (2012)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9568-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9568-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9568-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,24]],"date-time":"2019-08-24T04:15:59Z","timestamp":1566620159000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9568-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,13]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9568"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9568-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,13]]}}}