{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:36:03Z","timestamp":1725474963753},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540496946"},{"type":"electronic","value":"9783540496960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11940128_16","type":"book-chapter","created":{"date-parts":[[2006,11,29]],"date-time":"2006-11-29T00:57:35Z","timestamp":1164761855000},"page":"141-152","source":"Crossref","is-referenced-by-count":2,"title":["Algorithms on Graphs with Small Dominating Targets"],"prefix":"10.1007","author":[{"given":"Divesh","family":"Aggarwal","sequence":"first","affiliation":[]},{"given":"Chandan K.","family":"Dubey","sequence":"additional","affiliation":[]},{"given":"Shashank K.","family":"Mehta","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/3-540-61680-2_55","volume-title":"Algorithms - ESA \u201996","author":"S. Guha","year":"1996","unstructured":"Guha, S., Khuller, S.: Approximation Algorithms for Connected Dominating Sets. In: D\u00edaz, J. (ed.) ESA 1996. LNCS, vol.\u00a01136, pp. 179\u2013193. Springer, Heidelberg (1996)"},{"key":"16_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/3-540-57155-8_242","volume-title":"Algorithms and Data Structures","author":"H. Balakrishnan","year":"1993","unstructured":"Balakrishnan, H., Rajaraman, A., Rangan, C.P.: Connected Domination and Steiner Set on Asteroidal Triple-Free Graphs. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) WADS 1993. LNCS, vol.\u00a0709, pp. 131\u2013141. Springer, Heidelberg (1993)"},{"key":"16_CR3","series-title":"Lecture Notes in Computer Science","first-page":"770","volume-title":"Proceedings of SODA","author":"G. Robins","year":"2000","unstructured":"Robins, G., Zelikovsky, A.: Improved Steiner Tree Approximation in Graphs. In: Proceedings of SODA. LNCS, pp. 770\u2013779. Springer, Heidelberg (2000)"},{"key":"16_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1007\/978-3-540-49382-2_6","volume-title":"Proceedings of FSTTCS year","author":"S. Guha","year":"1998","unstructured":"Guha, S., Khuller, S.: Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets. In: Proceedings of FSTTCS year. LNCS, pp. 54\u201365. Springer, Heidelberg (1998)"},{"key":"16_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/BFb0023489","volume-title":"Proceedings of STACS","author":"H.J. Pr\u00f6mel","year":"1997","unstructured":"Pr\u00f6mel, H.J., Steger, A.: RNC-Approximation Algorithms for the Steiner Problem. In: Proceedings of STACS. LNCS, pp. 559\u2013570. Springer, Heidelberg (1997)"},{"key":"16_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/3-540-61332-3_167","volume-title":"Computing and Combinatorics","author":"A.E.F. Clementi","year":"1996","unstructured":"Clementi, A.E.F., Trevisan, L.: Improved Non-Approximability Results for Vertex Cover with Density Constraints. In: Cai, J.-Y., Wong, C.K. (eds.) COCOON 1996. LNCS, vol.\u00a01090, pp. 333\u2013342. Springer, Heidelberg (1996)"},{"key":"16_CR7","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1978","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, San Francisco (1978)"},{"key":"16_CR8","volume-title":"Complexity and Approximation","author":"G. Ausiello","year":"2003","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Springer, Heidelberg (2003)"},{"key":"16_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2363-2","volume-title":"On Optimal Interconnections for VLSI","author":"A.B. Kahng","year":"1995","unstructured":"Kahng, A.B., Robins, G.: On Optimal Interconnections for VLSI. Kluwer Academic, Dordrecht (1995)"},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Lee, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Caldwell, A., Kahng, A., Mantik, S., Markov, I., Zelikovsky, A.: On Wirelength Estimations for Row-Biased Placement. In: Proceedings of International Symposium on Physical Design, pp. 4\u201311 (1998)","DOI":"10.1145\/274535.274536"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s003730170043","volume":"17","author":"T. Kloks","year":"2001","unstructured":"Kloks, T., Kratsch, D., M\u00fcller, H.: On the Structure of Graphs with Bounded Asteroidal Number. Graphs and Combinatorics\u00a017, 295\u2013306 (2001)","journal-title":"Graphs and Combinatorics"},{"key":"16_CR13","unstructured":"Korte, B., Pr\u00f6mel, H.J., Steger, A.: Steiner Trees in VLSI Layouts. J. Paths flows and VLSI layout (1990)"},{"issue":"4","key":"16_CR14","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1002\/net.10097","volume":"42","author":"X. Cheng","year":"2003","unstructured":"Cheng, X., Huang, X., Li, D., Wu, W., Du, D.-Z.: A Polynomial-Time Approximation Scheme for the Minimum-Connected Dominating Set in Ad Hoc Wireless Networks. Journal of Networks\u00a042(4), 202\u2013208 (2003)","journal-title":"Journal of Networks"},{"issue":"3","key":"16_CR15","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1137\/S0895480193250125","volume":"10","author":"D.G. Corneil","year":"1997","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: Asteroidal Triple-Free Graphs. SIAM J. Discrete Math.\u00a010(3), 399\u2013430 (1997)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"16_CR16","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1145\/321707.321710","volume":"19","author":"S. Even","year":"1972","unstructured":"Even, S., Pnueli, A., Lempel, A.: Permutation Graphs and Transitive Graphs. J. ACM\u00a019(3), 400\u2013410 (1972)","journal-title":"J. ACM"},{"key":"16_CR17","first-page":"245","volume":"51","author":"C.G. Lekkerkerker","year":"1962","unstructured":"Lekkerkerker, C.G., Boland, J.Ch.: Boland: Representation of a Finite Graphs by a Set of Intervals on the Real Line. J. Fund. Math.\u00a051, 245\u2013264 (1962)","journal-title":"J. Fund. Math."},{"key":"16_CR18","unstructured":"Motwani, R.: Lecture Notes on Approximation Algorithms, Dept. of Comp. Sc., Stanford University, vol.\u00a0I (1992)"},{"key":"16_CR19","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/S0166-218X(03)00298-1","volume":"134","author":"F.V. Fomin","year":"2004","unstructured":"Fomin, F.V., Kratsch, D., M\u00fcller, H.: Algorithms for Graphs with Small Octopus. Journal of Discrete Applied Mathematics\u00a0134, 105\u2013128 (2004)","journal-title":"Journal of Discrete Applied Mathematics"},{"key":"16_CR20","series-title":"Lecture Notes in Computer Science","first-page":"709","volume-title":"Prodeedings of SODA","author":"D. Kratsch","year":"2003","unstructured":"Kratsch, D., Spinrad, J.: Between O(nm) and O(n \u03b1 ). In: Prodeedings of SODA. LNCS, pp. 709\u2013716. Springer, Heidelberg (2003)"},{"key":"16_CR21","unstructured":"Habib, M.: Substitution des Structures Combinatoires, Theorie et Algorithmes. These D\u2019etat, Paris VI (1981)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11940128_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:49:44Z","timestamp":1619495384000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11940128_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540496946","9783540496960"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11940128_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}