{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T07:33:13Z","timestamp":1769844793621,"version":"3.49.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,9,30]],"date-time":"2009-09-30T00:00:00Z","timestamp":1254268800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2010,8]]},"DOI":"10.1007\/s11590-009-0146-5","type":"journal-article","created":{"date-parts":[[2009,9,29]],"date-time":"2009-09-29T06:24:42Z","timestamp":1254205482000},"page":"311-320","source":"Crossref","is-referenced-by-count":14,"title":["Approximation algorithms for finding and partitioning unit-disk graphs into co-k-plexes"],"prefix":"10.1007","volume":"4","author":[{"given":"Balabhaskar","family":"Balasundaram","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shyam Sundar","family":"Chandramouli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Svyatoslav","family":"Trukhanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,9,30]]},"reference":[{"key":"146_CR1","first-page":"33","volume":"47","author":"J. Andrews","year":"1985","unstructured":"Andrews J., Jacobson M.: On a generalization of chromatic number. Congressus Numerantium 47, 33\u201348 (1985)","journal-title":"Congressus Numerantium"},{"key":"146_CR2","unstructured":"Balasundaram, B.: Graph theoretic generalizations of clique: optimization and extensions. Ph.D. dissertation, Texas A&M University (2007)"},{"key":"146_CR3","volume-title":"Encyclopedia of Optimization.","author":"B. Balasundaram","year":"2008","unstructured":"Balasundaram B., Butenko S.: Optimization problems in unit-disk graphs. In: Floudas, C.A., Pardalos, P.M. (eds) Encyclopedia of Optimization., Springer Science+Business Media, New York (2008) (to appear)"},{"key":"146_CR4","unstructured":"Balasundaram, B., Butenko, S., Hicks, I.V.: Clique relaxations in social network analysis: the maximum k-plex problem (2008). http:\/\/iem.okstate.edu\/baski\/files\/kplex4web.pdf (submitted)"},{"issue":"1\u20132","key":"146_CR5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0925-7721(97)00014-X","volume":"9","author":"H. Breu","year":"1998","unstructured":"Breu H., Kirkpatrick D.G.: Unit disk graph recognition is NP-hard. Comput. Geom. Theory Appl. 9(1\u20132), 3\u201324 (1998)","journal-title":"Comput. Geom. Theory Appl."},{"key":"146_CR6","doi-asserted-by":"crossref","unstructured":"Cerioli, M.R., Faria, L., Ferreira, T.O., Protti, F.: On minimum clique partition and maximum independent set on unit disk graphs and penny graphs: complexity and approximation. In: Latin-American Conference on Combinatorics, Graphs and Applications, Electronic Notes in Discrete Mathematics, vol. 18, pp. 73\u201379 (electronic). Elsevier, Amsterdam (2004)","DOI":"10.1016\/j.endm.2004.06.012"},{"key":"146_CR7","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"B.N. Clark","year":"1990","unstructured":"Clark B.N., Colbourn C.J., Johnson D.S.: Unit disk graphs. Discrete Math. 86, 165\u2013177 (1990)","journal-title":"Discrete Math."},{"key":"146_CR8","volume-title":"Combinatorial Optimization","author":"W. Cook","year":"1998","unstructured":"Cook W., Cunningham W., Pulleyblank W., Schrijver A.: Combinatorial Optimization. Wiley, New York (1998)"},{"key":"146_CR9","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1002\/jgt.3190100207","volume":"10","author":"L. Cowen","year":"1986","unstructured":"Cowen L., Cowen R., Woodall D.: Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valence. J. Graph Theory 10, 187\u2013195 (1986)","journal-title":"J. Graph Theory"},{"issue":"3","key":"146_CR10","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1002\/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T","volume":"24","author":"L. Cowen","year":"1997","unstructured":"Cowen L., Goddard W., Jesurum C.E.: Defective coloring revisited. J. Graph Theory 24(3), 205\u2013219 (1997)","journal-title":"J. Graph Theory"},{"key":"146_CR11","doi-asserted-by":"crossref","unstructured":"Dessmark, A., Jansen, K., Lingas, A.: The maximum k-dependent and f-dependent set problem. In: Ng, K.W., Raghavan, P., Balasubramanian, N.V., Chin, F.Y.L. (eds.) Proceedings of the 4th International Symposium on Algorithms and Computation: ISAAC \u201993. Lecture Notes in Computer Science, vol. 762, pp. 88\u201397. Springer, Berlin (1993)","DOI":"10.1007\/3-540-57568-5_238"},{"key":"146_CR12","unstructured":"Djidev, H., Garrido, O., Levcopoulos, C., Lingas, A.: On the maximum k-dependent set problem. Tech. Rep. LU-CS-TR:92-91, Dept. of Computer Science, Lund University, Sweden (1992)"},{"key":"146_CR13","first-page":"135","volume-title":"Efficient Approximation and Online Algorithms. Lecture Notes in Computer Science, vol. 3484","author":"T. Erlebach","year":"2006","unstructured":"Erlebach T., Fiala J.: Independence and coloring problems on intersection graphs of disks. In: Bampis, E., Jansen, K., Kenyon, C. (eds) Efficient Approximation and Online Algorithms. Lecture Notes in Computer Science, vol. 3484, pp. 135\u2013155. Springer, Heidelberg (2006)"},{"key":"146_CR14","doi-asserted-by":"crossref","unstructured":"Fishkin, A.V.: Disk graphs: a short survey. In: Jansen, K., Solis-Oba, R. (eds.) Approximation and Online Algorithms. Lecture Notes in Computer Science, vol. 2909, pp. 260\u2013264. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-24592-6_23"},{"key":"146_CR15","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. W.H. Freeman and Company, New York (1979)"},{"issue":"12","key":"146_CR16","doi-asserted-by":"crossref","first-page":"1497","DOI":"10.1109\/PROC.1980.11899","volume":"68","author":"W.K. Hale","year":"1980","unstructured":"Hale W.K.: Frequency assignment: theory and applications. Proc IEEE 68(12), 1497\u20131514 (1980)","journal-title":"Proc IEEE"},{"key":"146_CR17","first-page":"205","volume":"50","author":"F. Harary","year":"1985","unstructured":"Harary F., Jones K.: Conditional colorability ii: Bipartite variations. Congressus Numerantium 50, 205\u2013218 (1985)","journal-title":"Congressus Numerantium"},{"key":"146_CR18","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad J.: Clique is hard to approximate within $${n^{1-\\epsilon}}$$ . Acta Math. 182, 105\u2013142 (1999)","journal-title":"Acta Math."},{"key":"146_CR19","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/j.endm.2005.06.022","volume":"22","author":"F. Havet","year":"2005","unstructured":"Havet F., Kang R.J., Sereni J.S.: Improper colouring of unit disk graphs. Elect. Notes Discrete Math. 22, 123\u2013128 (2005)","journal-title":"Elect. Notes Discrete Math."},{"key":"146_CR20","unstructured":"Havet, F., Kang, R.J., Sereni, J.S.: Improper colouring of unit disk graphs. Tech. Rep. RR-6206, Institute National de Recherche en Informatique et en Automatique (INRIA), France (2007) Networks (to appear). http:\/\/hal.inria.fr\/inria-00150464_v2\/"},{"issue":"3","key":"146_CR21","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D.S. Hochbaum","year":"1983","unstructured":"Hochbaum D.S.: Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Appl. Math. 6(3), 243\u2013254 (1983)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"146_CR22","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"H.B. Hunt","year":"1998","unstructured":"Hunt H.B., Marathe M.V., Radhakrishnan V., Ravi S.S., Rosenkrantz D.J., Stearns R.E.: NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J. Algorithms 26(2), 238\u2013274 (1998)","journal-title":"J. Algorithms"},{"key":"146_CR23","unstructured":"Kang, R.: Improper coloring of graphs. Ph.D. dissertation, University of Oxford (2007)"},{"issue":"2","key":"146_CR24","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1145\/263876.263885","volume":"27","author":"P. Krishna","year":"1997","unstructured":"Krishna P., Vaidya N.H., Chatterjee M., Pradhan D.K.: A cluster-based approach for routing in dynamic networks. ACM SIGCOMM Comp. Commun. Rev. 27(2), 49\u201364 (1997)","journal-title":"ACM SIGCOMM Comp. Commun. Rev."},{"key":"146_CR25","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/net.3230250205","volume":"25","author":"M.V. Marathe","year":"1995","unstructured":"Marathe M.V., Breu H., Hunt H.B. III, Ravi S.S., Rosenkrantz D.J.: Simple heuristics for unit disk graphs. Networks 25, 59\u201368 (1995)","journal-title":"Networks"},{"key":"146_CR26","doi-asserted-by":"crossref","unstructured":"Ramaswami, R., Parhi, K.K.: Distributed scheduling of broadcasts in a radio network. In: Proceedings of the Eighth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM \u201989), vol. 2, pp. 497\u2013504 (1989)","DOI":"10.1109\/INFCOM.1989.101493"},{"key":"146_CR27","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1080\/0022250X.1978.9989883","volume":"6","author":"S.B. Seidman","year":"1978","unstructured":"Seidman S.B., Foster B.L.: A graph theoretic generalization of the clique concept. J. Math. Sociol. 6, 139\u2013154 (1978)","journal-title":"J. Math. Sociol."},{"key":"146_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0021-9800(68)80081-X","volume":"4","author":"G. Szekeres","year":"1968","unstructured":"Szekeres G., Wilf H.S.: An inequality for the chromatic number of a graph. J. Comb. Theory 4, 1\u20133 (1968)","journal-title":"J. Comb. Theory"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-009-0146-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-009-0146-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-009-0146-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,3]],"date-time":"2019-06-03T15:15:03Z","timestamp":1559574903000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-009-0146-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9,30]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["146"],"URL":"https:\/\/doi.org\/10.1007\/s11590-009-0146-5","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9,30]]}}}