{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:30:59Z","timestamp":1725517859013},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540853626"},{"type":"electronic","value":"9783540853633"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85363-3_4","type":"book-chapter","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T19:29:28Z","timestamp":1219865368000},"page":"35-48","source":"Crossref","is-referenced-by-count":1,"title":["Connected Vertex Covers in Dense Graphs"],"prefix":"10.1007","author":[{"given":"Jean","family":"Cardinal","sequence":"first","affiliation":[]},{"given":"Eythan","family":"Levy","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear steiner tree problem is NP complete. SIAM Journal of Applied Mathematics\u00a032, 826\u2013834 (1977)","journal-title":"SIAM Journal of Applied Mathematics"},{"issue":"5","key":"4_CR2","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0020-0190(82)90022-9","volume":"14","author":"C.D. Savage","year":"1982","unstructured":"Savage, C.D.: Depth-first search and the vertex cover problem. Inf. Process. Lett.\u00a014(5), 233\u2013237 (1982)","journal-title":"Inf. Process. Lett."},{"key":"4_CR3","unstructured":"Fernau, H., Manlove, D.: Vertex and edge covers with clustering properties: Complexity and algorithms. In: Algorithms and Complexity in Durham 2006 - Proceedings of the Second ACiD Workshop, Durham, UK, 18-20 September 2006, pp. 69\u201384 (2006)"},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1007\/978-3-540-74839-7_20","volume-title":"Proc. of the 33rd International Workshop on Graph-Theoretic Aspects in Computer Science (WG 2007)","author":"B. Escoffier","year":"2007","unstructured":"Escoffier, B., Gourv\u00e8s, L., Monnot, J.: Complexity and approximation results for the connected vertex cover problem. In: Brandst\u00e4dt, A., Kratsch, D., M\u00fcller, H. (eds.) WG 2007. LNCS, vol.\u00a04769, pp. 202\u2013213. Springer, Heidelberg (2007)"},{"issue":"2","key":"4_CR5","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.ipl.2004.01.011","volume":"90","author":"T. Fujito","year":"2004","unstructured":"Fujito, T., Doi, T.: A 2-approximation NC algorithm for connected vertex cover and tree cover. Inf. Process. Lett.\u00a090(2), 59\u201363 (2004)","journal-title":"Inf. Process. Lett."},{"key":"4_CR6","unstructured":"Moser, H.: Exact algorithms for generalizations of vertex cover. Master\u2019s thesis, Institut f\u00fcr Informatik, Friedrich-Schiller Universit\u00e4t Jena (2005)"},{"issue":"3","key":"4_CR7","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 Comput. Syst.\u00a041(3), 501\u2013520 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"4_CR8","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/s00224-007-9089-3","volume":"43","author":"D. M\u00f6lle","year":"2008","unstructured":"M\u00f6lle, D., Richter, S., Rossmanith, P.: Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. Theory Comput. Syst.\u00a043(2), 234\u2013253 (2008)","journal-title":"Theory Comput. Syst."},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Karpinski, M., Zelikovsky, A.: Approximating dense cases of covering problems. In: Pardalos, P., Du, D. (eds.) Proc. 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":"4_CR10","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":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1007\/11533719_71","volume-title":"Computing and Combinatorics","author":"J. Cardinal","year":"2005","unstructured":"Cardinal, J., Labb\u00e9, M., Langerman, S., Levy, E., M\u00e9lot, H.: A tight analysis of the maximal matching heuristic. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 701\u2013709. Springer, Heidelberg (2005)"},{"key":"4_CR12","unstructured":"Imamura, T., Iwama, K.: Approximating vertex cover on dense graphs. In: Proc. of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 582\u2013589 (2005)"},{"key":"4_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/11970125_9","volume-title":"Approximation and Online Algorithms","author":"J. Cardinal","year":"2007","unstructured":"Cardinal, J., Langerman, S., Levy, E.: Improved approximation bounds for edge dominating set in dense graphs. In: Erlebach, T., Kaklamanis, C. (eds.) WAOA 2006. LNCS, vol.\u00a04368, pp. 108\u2013120. Springer, Heidelberg (2007)"},{"issue":"3","key":"4_CR14","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1007\/s00453-001-0012-z","volume":"30","author":"M. Karpinski","year":"2001","unstructured":"Karpinski, M.: Polynomial time approximation schemes for some dense instances of NP-hard optimization problems. Algorithmica\u00a030(3), 386\u2013397 (2001)","journal-title":"Algorithmica"},{"issue":"4","key":"4_CR15","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1016\/j.jcss.2004.03.006","volume":"69","author":"R. Bar-Yehuda","year":"2004","unstructured":"Bar-Yehuda, R., Kehat, Z.: Approximating the dense set-cover problem. J. Comput. Syst. Sci.\u00a069(4), 547\u2013561 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Paul, S., Miller, R.E.: Locating faults in a systematic manner in a large heterogeneous network. In: Proc. IEEE INFOCOM 1995, The Conference on Computer Communications. Fourteenth Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 522\u2013529 (1995)","DOI":"10.1109\/INFCOM.1995.515917"},{"issue":"2","key":"4_CR17","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s10732-005-0433-y","volume":"11","author":"V. Grout","year":"2005","unstructured":"Grout, V.: Principles of cost minimisation in wireless networks. J. Heuristics\u00a011(2), 115\u2013133 (2005)","journal-title":"J. Heuristics"},{"issue":"3","key":"4_CR18","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1109\/TC.2006.40","volume":"55","author":"J. Wu","year":"2006","unstructured":"Wu, J., Lou, W., Dai, F.: Extended multipoint relays to determine connected dominating sets in MANETs. IEEE Trans. Computers\u00a055(3), 334\u2013347 (2006)","journal-title":"IEEE Trans. Computers"},{"issue":"7","key":"4_CR19","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1109\/TMC.2007.1034","volume":"6","author":"M.T. Thai","year":"2007","unstructured":"Thai, M.T., F.W.,, Liu, D., Zhu, S., Du, D.: Connected dominating sets in wireless networks with different transmission ranges. IEEE Trans. Mob. Comput\u00a06(7), 721\u2013730 (2007)","journal-title":"IEEE Trans. Mob. Comput"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"M\u00e9lot, H.: Facet Defining Inequalities among Graph Invariants: the system GraPHedron. Discrete Applied Mathematics (to appear, 2007)","DOI":"10.1016\/j.dam.2007.09.005"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85363-3_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:24:21Z","timestamp":1606184661000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85363-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540853626","9783540853633"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85363-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}