{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:38:00Z","timestamp":1725489480903},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540414131"},{"type":"electronic","value":"9783540444503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44450-5_9","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T04:26:08Z","timestamp":1187238368000},"page":"117-126","source":"Crossref","is-referenced-by-count":2,"title":["On Approximability of the Independent\/Connected Edge Dominating Set Problems"],"prefix":"10.1007","author":[{"given":"Toshihiro","family":"Fujito","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,11,24]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag, Berlin Heidelberg New York (1999)"},{"key":"9_CR2","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0020-0190(93)90072-H","volume":"47","author":"E.M. Arkin","year":"1993","unstructured":"Arkin, E.M., Halld\u00f3rsson, M.M., Hassin, R.: Approximating the tree and tour covers of a graph. IPL 47 (1993) 275\u2013282","journal-title":"IPL"},{"key":"9_CR3","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. In: Annals of Discrete Mathematics, Vol. 25. North-Holland (1985) 27\u201346","journal-title":"Annals of Discrete Mathematics"},{"key":"9_CR4","unstructured":"Carr, R., Fujito, T., Konjevod, G., Parekh, O.: A 21\/10-approximation algorithm for a generalization of the weighted edge-dominating set problem. In: Proc. 8th ESA (to appear)"},{"key":"9_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1007\/BFb0030875","volume-title":"Structure in approximation classes","author":"P. Crescenzi","year":"1995","unstructured":"Crescenzi, P., Kann, V., Silvestri, R., Trevisan, L.: Structure in approximation classes. In: Proc. COCOON 95. Lecture Notes in Computer Science, Vol. 959. Springer-Verlag (1995) 539\u2013548"},{"key":"9_CR6","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. In: Proc. the Twenty-Eighth Annual ACM Symp. Theory of Computing. ACM (1996) 314\u2013318"},{"key":"9_CR7","unstructured":"Fujito, T., Nagamochi, H.: Polyhedral characterizations and a 2-approximation algorithm for the edge dominating set problem. (submitted)"},{"issue":"4","key":"9_CR8","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 J. Applied Math. 32(4) (1977) 826\u2013834","journal-title":"SIAM J. Applied Math"},{"issue":"4","key":"9_CR9","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/PL00009201","volume":"20","author":"S. Guha","year":"1998","unstructured":"Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20(4) (1998) 374\u2013387","journal-title":"Algorithmica"},{"key":"9_CR10","unstructured":"Guha, S., Khuller, S.: Improved methods for approximating node weighted Steiner trees and connected dominating sets. Information and Computation (to appear)"},{"key":"9_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M. Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, Berlin (1988)"},{"key":"9_CR12","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. IPL 46 (1993) 169\u2013172","journal-title":"IPL"},{"key":"9_CR13","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F. Harary","year":"1969","unstructured":"Harary, F.: Graph Theory. Addison-Wesley, Reading, MA (1969)"},{"issue":"3","key":"9_CR14","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1137\/0406030","volume":"6","author":"J.D. Horton","year":"1993","unstructured":"Horton, J.D., Kilakos, K.: Minimum edge dominating sets. SIAM J. Discrete Math. 6(3) (1993) 375\u2013387","journal-title":"SIAM J. Discrete Math"},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0020-0190(91)90188-N","volume":"37","author":"R.W. Irving","year":"1991","unstructured":"Irving, R.W.: On approximating the minimum independent dominating set. IPL 37 (1991) 197\u2013200","journal-title":"IPL"},{"key":"9_CR16","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.): Complexity of Computer Computations. Plenum Press, New York (1972) 85\u2013103"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Koenemann, J., Konjevod, G., Parekh, O., Sinha, A.: Improved approximations for tour and tree covers. In: Proc. APPROX 2000 (to appear)","DOI":"10.1007\/3-540-44436-X_19"},{"issue":"1","key":"9_CR18","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1006\/jagm.1995.1029","volume":"19","author":"P. Klein","year":"1995","unstructured":"Klein, P., Ravi, R.: A nearly best-possible approximation algorithm for nodeweighted Steiner trees. J. Algorithms 19(1) (1995) 104\u2013115","journal-title":"J. Algorithms"},{"key":"9_CR19","unstructured":"Orponen, P., Mannila, H.: On approximation preserving reductions: Complete problems and robust measures. Technical Report C-1987-28, Department of Computer Science, University of Helsinki (1987)"},{"key":"9_CR20","unstructured":"Rajagopalan, S., Vazirani, V.V.: On the bidirected cut relaxation for the metric Steiner tree problem. In: Proc. 10th Annual ACM-SIAM Symp. Discrete Algorithms. ACM-SIAM (1999) 742\u2013751"},{"key":"9_CR21","unstructured":"Robins, G., Zelikovsky, A.: Improved Steiner tree approximation in graphs. In: Proc. 11th Annual ACM-SIAM Symp. Discrete Algorithms. ACM-SIAM (2000) 770\u2013779"},{"issue":"5","key":"9_CR22","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0020-0190(82)90022-9","volume":"14","author":"C. Savage","year":"1982","unstructured":"Savage, C.: Depth-first search and the vertex cover problem. IPL 14(5) (1982) 233\u2013235","journal-title":"IPL"},{"issue":"2","key":"9_CR23","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02579435","volume":"4","author":"L.A. Wolsey","year":"1982","unstructured":"Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 4(2) (1982) 385\u2013393","journal-title":"Combinatorica"},{"issue":"3","key":"9_CR24","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. Applied Math. 38(3) (1980) 364\u2013372","journal-title":"SIAM J. Applied Math"}],"container-title":["Lecture Notes in Computer Science","FST TCS 2000: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44450-5_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T22:23:03Z","timestamp":1550787783000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44450-5_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540414131","9783540444503"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-44450-5_9","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}