{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:11:12Z","timestamp":1725567072618},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540280613"},{"type":"electronic","value":"9783540318064"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11533719_71","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T13:34:13Z","timestamp":1127828053000},"page":"701-709","source":"Crossref","is-referenced-by-count":12,"title":["A Tight Analysis of the Maximal Matching Heuristic"],"prefix":"10.1007","author":[{"given":"Jean","family":"Cardinal","sequence":"first","affiliation":[]},{"given":"Martine","family":"Labb\u00e9","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Langerman","sequence":"additional","affiliation":[]},{"given":"Eythan","family":"Levy","sequence":"additional","affiliation":[]},{"given":"Hadrien","family":"M\u00e9lot","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"71_CR1","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. Ann. Discrete Math.\u00a025, 27\u201345 (1985)","journal-title":"Ann. Discrete Math."},{"key":"71_CR2","doi-asserted-by":"crossref","unstructured":"Cardinal, J., Labb\u00e9, M., Langerman, S., Levy, E., M\u00e9lot, H.: A tight analysis of the maximal matching heuristic. Technical Report 545, Universit\u00e9 Libre de Bruxelles (2005), Available at http:\/\/www.ulb.ac.be\/di\/publications","DOI":"10.1007\/11533719_71"},{"key":"71_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/978-3-540-24587-2_43","volume-title":"Algorithms and Computation","author":"M. Chleb\u2018\u0131k","year":"2003","unstructured":"Chleb\u2018\u0131k, M., Chleb\u2018\u0131kov\u00e1, J.: Approximation hardness of minimum edge dominating set and minimum maximal matching. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol.\u00a02906, pp. 415\u2013424. Springer, Heidelberg (2003)"},{"key":"71_CR4","unstructured":"Christophe, J., Dewez, S., Doignon, J., Elloumi, S., Fasbender, G., Gr\u00e9goire, P., Huygens, D., Labb\u00e9, M., M\u00e9lot, H., Yaman, H.: Linear inequalities among graph invariants: using GraPHedron to uncover optimal relationships (2004) (submitted), Available at http:\/\/www.optimization-online.org\/DBHTML\/2004\/09\/964.html"},{"issue":"1-2","key":"71_CR5","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0304-3975(97)00226-0","volume":"225","author":"A. Clementi","year":"1999","unstructured":"Clementi, A., Trevisan, L.: Improved non-approximability results for vertex cover problems with density constraints. Theoretical Computer Science\u00a0225(1-2), 113\u2013128 (1999)","journal-title":"Theoretical Computer Science"},{"key":"71_CR6","volume-title":"Graph Theory, Second Edition","author":"R. Diestel","year":"2000","unstructured":"Diestel, R.: Graph Theory, Second Edition. Springer, Heidelberg (2000)"},{"key":"71_CR7","volume-title":"Proceedings of SOR","author":"A.V. Eremeev","year":"1999","unstructured":"Eremeev, A.V.: On some approximation algorithms for dense vertex cover problem. In: Proceedings of SOR, Springer, Heidelberg (1999)"},{"key":"71_CR8","volume-title":"Computers and intractability. A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. A guide to the theory of NP-completeness. Freeman and Company, New York (1979)"},{"key":"71_CR9","doi-asserted-by":"publisher","first-page":"1608","DOI":"10.1137\/S0097539700381097","volume":"31","author":"E. Halperin","year":"2002","unstructured":"Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM Journal on Computing\u00a031, 1608\u20131623 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"71_CR10","unstructured":"Hansen, P., M\u00e9lot, H.: Variable neighborhood search for extremal graphs 9. Bounding the irregularity of a graph. To appear in S. Fajtlowicz et al (Eds.), Graphs and Discovery, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Providence, American Mathematical Society"},{"key":"71_CR11","doi-asserted-by":"crossref","unstructured":"Hastad, J.: Some optimal inapproximability results. In: Proceedings of the Twenty- Ninth Annual ACM Symposium on Theory of Computing, pp. 1\u201310 (1997)","DOI":"10.1145\/258533.258536"},{"key":"71_CR12","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/BF03167363","volume":"16","author":"T. Ibaraki","year":"1999","unstructured":"Ibaraki, T., Nagamochi, H.: An approximation of the minimum vertex cover in a graph. Japan J. Indust. Appl. Math.\u00a016, 369\u2013375 (1999)","journal-title":"Japan J. Indust. Appl. Math."},{"key":"71_CR13","unstructured":"Imamura, T., Iwama, K.: Approximating vertex cover on dense graphs. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, SODA (2005)"},{"key":"71_CR14","unstructured":"Karakostas, G.: A better approximation ratio for the vertex cover problem. ECCC Report TR04-084 (2004)"},{"key":"71_CR15","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Zelikovsky, A.: Approximating dense cases of covering problems. In: Pardalos, P., Du, D. (eds.) Proceedings of the DIMACS Workshop on Network Design: Connectivity and Facilites Location. DIMACS series in Disc. Math. and Theor. Comp. Sci., vol.\u00a040, pp. 169\u2013178 (1997)","DOI":"10.1090\/dimacs\/040\/11"},{"key":"71_CR16","unstructured":"M\u00e9lot, H.: Facets defining inequalities among graph invariants: the system GraPHedron (In preparation)"},{"key":"71_CR17","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF00290149","volume":"22","author":"B. Monien","year":"1985","unstructured":"Monien, B., Speckenmeyer, E.: Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Inf.\u00a022, 115\u2013123 (1985)","journal-title":"Acta Inf."},{"issue":"3","key":"71_CR18","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. System. Sci.\u00a043(3), 425\u2013440 (1991)","journal-title":"J. Comput. System. Sci."},{"issue":"3","key":"71_CR19","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M. Yannakakis","year":"1980","unstructured":"Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math.\u00a038(3), 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11533719_71","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T22:37:35Z","timestamp":1586471855000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11533719_71"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540280613","9783540318064"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/11533719_71","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}