{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:07:47Z","timestamp":1758823667000},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2011,3,17]],"date-time":"2011-03-17T00:00:00Z","timestamp":1300320000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2011,5]]},"DOI":"10.1007\/s00373-011-1026-1","type":"journal-article","created":{"date-parts":[[2011,3,16]],"date-time":"2011-03-16T05:27:53Z","timestamp":1300253273000},"page":"399-411","source":"Crossref","is-referenced-by-count":19,"title":["Minimum Clique Partition in Unit Disk Graphs"],"prefix":"10.1007","volume":"27","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[]},{"given":"J\u00e1nos","family":"Pach","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,3,17]]},"reference":[{"key":"1026_CR1","doi-asserted-by":"crossref","unstructured":"Amb\u00fchl, C., Erlebach, T., Mihal\u00e1k, M., Nunkesser, M.: Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. In: Proceedings of APPROX-RANDOM. Lecture Notes in Computer Science, vol. 4110, pp. 3\u201314. Springer, Berlin (2006)","DOI":"10.1007\/11830924_3"},{"key":"1026_CR2","doi-asserted-by":"crossref","unstructured":"Balasundaram, B., Butenko, S.: Optimization problems in unit-disk graphs. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, pp. 2832\u20132844. Springer, Berlin (2008)","DOI":"10.1007\/978-0-387-74759-0_486"},{"key":"1026_CR3","unstructured":"Breu, H.: Algorithmic aspects of constrained unit disk graphs, PhD Thesis, University of British Columbia, (1996)"},{"issue":"1\u20132","key":"1026_CR4","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.: Unit disk graph recognition is NP-hard. Comput. Geom. Theory Appl. 9(1\u20132), 3\u201324 (1998)","journal-title":"Comput. Geom. Theory Appl."},{"key":"1026_CR5","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1016\/0196-6774(91)90007-L","volume":"12","author":"V. Capolyleas","year":"1991","unstructured":"Capolyleas V., Rote G., Woeginger G.: Geometric clusterings. J. Algorithms 12, 341\u2013356 (1991)","journal-title":"J. Algorithms"},{"key":"1026_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-62035-5","volume-title":"An Introduction to the Geometry of Numbers","author":"J. Cassels","year":"1959","unstructured":"Cassels J.: An Introduction to the Geometry of Numbers. Springer, New York (1959)"},{"key":"1026_CR7","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.endm.2004.06.012","volume":"18","author":"M.R. Cerioli","year":"2004","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. Electron. Notes Discret. Math. 18, 73\u201379 (2004)","journal-title":"Electron. Notes Discret. Math."},{"key":"1026_CR8","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"B. Clark","year":"1990","unstructured":"Clark B., Colbourn C., Johnson D.: Unit disk graphs. Discret. Math. 86, 165\u2013177 (1990)","journal-title":"Discret. Math."},{"key":"1026_CR9","unstructured":"Dumitrescu, A., Pach, J.: Minimum clique partition in unit disk graphs, preprint, September 8, 2009. arXiv:0909.1552v1"},{"key":"1026_CR10","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0012-365X(90)90147-A","volume":"81","author":"H. Edelsbrunner","year":"1990","unstructured":"Edelsbrunner H., Robison A., Shen X.-J.: Covering convex sets with non-overlapping polygons. Discret. Math. 81, 153\u2013164 (1990)","journal-title":"Discret. Math."},{"key":"1026_CR11","unstructured":"Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric graphs. In: Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms, pp. 671\u2013679 (2001)"},{"key":"1026_CR12","unstructured":"Erlebach, T., Leeuwen, E.J.: Approximating geometric coverage problems. In: Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms, pp. 1267\u20131276 (2008)"},{"key":"1026_CR13","doi-asserted-by":"crossref","unstructured":"Feder, T., Greene, D.: Optimal algorithms for approximate clustering. In: Proceedings of the 20th ACM Symposium on Theory of Computing, pp. 434\u2013444 (1988)","DOI":"10.1145\/62212.62255"},{"key":"1026_CR14","first-page":"62","volume":"12\/A","author":"L. Fejes T\u00f3th","year":"1950","unstructured":"Fejes T\u00f3th L.: Some packing and covering theorems. Acta Scientiarum Mathematicarum (Szeged) 12\/A, 62\u201367 (1950)","journal-title":"Acta Scientiarum Mathematicarum (Szeged)"},{"key":"1026_CR15","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"issue":"1","key":"1026_CR16","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0020-0190(93)90246-6","volume":"45","author":"M.M. Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson M.M.: A still better performance guarantee for approximate graph coloring. Inform. Process. Lett. 45(1), 19\u201323 (1993)","journal-title":"Inform. Process. Lett."},{"key":"1026_CR17","volume-title":"An Introduction to the Theory of Numbers","author":"G.H. Hardy","year":"1979","unstructured":"Hardy G.H., Wright E.M.: An Introduction to the Theory of Numbers, 5th edn. Oxford University Press, New York (1979)","edition":"5th edn"},{"key":"1026_CR18","first-page":"363","volume":"8","author":"A. Heppes","year":"1964","unstructured":"Heppes A.: Filling a domain by disks. Periodica Mathematica Hungarica 8, 363\u2013371 (1964)","journal-title":"Periodica Mathematica Hungarica"},{"key":"1026_CR19","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":"1026_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing","author":"M. Mitzenmacher","year":"2005","unstructured":"Mitzenmacher M., Upfal E.: Probability and Computing. Cambridge University Press, London (2005)"},{"issue":"4","key":"1026_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1383369.1383380","volume":"4","author":"T. Nieberg","year":"2008","unstructured":"Nieberg T., Hurink J., Kern W.: Approximation schemes for wireless networks. ACM Trans. Algorithms 4(4), 1\u201317 (2008)","journal-title":"ACM Trans. Algorithms"},{"key":"1026_CR22","doi-asserted-by":"crossref","DOI":"10.1002\/9781118033203","volume-title":"Combinatorial Geometry","author":"J. Pach","year":"1995","unstructured":"Pach J., Agarwal P.K.: Combinatorial Geometry. John Wiley, New York (1995)"},{"key":"1026_CR23","doi-asserted-by":"crossref","unstructured":"Pirwani, I., Salavatipour, M.: A PTAS for minimum clique partition in unit disk graphs, preprint, April 14, 2009. arXiv:0904.2203v1","DOI":"10.1007\/978-3-642-13731-0_19"},{"key":"1026_CR24","doi-asserted-by":"crossref","unstructured":"Pirwani, I., Salavatipour, M.: A weakly robust PTAS for minimum clique partition in unit disk graphs, preprint, December 3, 2009. arXiv:0904.2203v2","DOI":"10.1007\/978-3-642-13731-0_19"},{"key":"1026_CR25","doi-asserted-by":"crossref","unstructured":"Pirwani, I., Salavatipour, M.: A weakly robust PTAS for minimum clique partition in unit disk graphs. In: Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21\u201323, 2010, LNCS, Vol. 6139, pp. 188\u2013199. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-13731-0_19"},{"key":"1026_CR26","unstructured":"Supowit, K.J.: Topics in computational geometry, PhD Thesis, University of Illinois at Urbana-Champaign, Report UIUCDCS-R-81-1062 (1981)"},{"issue":"1","key":"1026_CR27","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D. Zuckerman","year":"2007","unstructured":"Zuckerman D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-011-1026-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-011-1026-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-011-1026-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,9]],"date-time":"2019-06-09T08:15:12Z","timestamp":1560068112000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-011-1026-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,17]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,5]]}},"alternative-id":["1026"],"URL":"https:\/\/doi.org\/10.1007\/s00373-011-1026-1","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3,17]]}}}