{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T23:36:01Z","timestamp":1779233761256,"version":"3.51.4"},"reference-count":31,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":4242,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1995,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Unit disk graphs are intersection graphs of circles of unit radius in the plane. We present simple and provably good heuristics for a number of classical NP\u2010hard optimization problems on unit disk graphs. The problems considered include maximum independent set, minimum vertex cover, minimum coloring, and minimum dominating set. We also present an on\u2010line coloring heuristic which achieves a competitive ratio of 6 for unit disk graphs. Our heuristics do not need a geometric representation of unit disk graphs. Geometric representations are used only in establishing the performance guarantees of the heuristics. Several of our approximation algorithms can be extended to intersection graphs of circles of arbitrary radii in the plane, intersection graphs of regular polygons, and intersection graphs of higher dimensional regular objects.<\/jats:p>","DOI":"10.1002\/net.3230250205","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T19:21:47Z","timestamp":1178997707000},"page":"59-68","source":"Crossref","is-referenced-by-count":360,"title":["Simple heuristics for unit disk graphs"],"prefix":"10.1002","volume":"25","author":[{"given":"M. V.","family":"Marathe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H.","family":"Breu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"suffix":"III","given":"H. B.","family":"Hunt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. S.","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D. J.","family":"Rosenkrantz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"S.Arora C.Lund R.Motwani M.Sudan andM.Szegedy Proof verification and hardness of approximation problems.Proceedings of the 33rd Annual Symposium on Foundations of Computer Science(FOCS 1992) Pittsburgh PA (Oct.1992)14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"B. S.Baker Approximation algorithms for NP\u2010complete problems on planar graphs.Proceedings of the 24th Annual Symposium on Foundations of Computer Science(FOCS1983) Tucson AZ (Nov.1983)265\u2013273.","DOI":"10.1109\/SFCS.1983.7"},{"issue":"1","key":"e_1_2_1_3_3","first-page":"155","volume":"41","year":"1994","journal-title":"J. ACM"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"R.Bar\u2010YehudaandS.Even On approximating a vertex cover for planar graphs.Proceedings of the 14th Annual ACM Symposium on Theory of Computing(May1982)303\u2013309.","DOI":"10.1145\/800070.802205"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73101-3"},{"key":"e_1_2_1_6_2","series-title":"Technical Report 93\u201327","volume-title":"Unit disk graph recognition is NP\u2010hard","author":"Breu H.","year":"1993"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90358-O"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2016-7"},{"key":"e_1_2_1_9_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_10_2","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic M. C.","year":"1980"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120212"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1980.11899"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90080-X"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"e_1_2_1_15_2","doi-asserted-by":"crossref","unstructured":"H. B.HuntIII M. V.Marathe V.Radhakrishnan S. S.Ravi D. J.Rosenkrantz andR. E.Stearns A unified approach to approximation schemes for NP\u2010 and PSPACE\u2010hard problems for geometric graphs.Proceedings of the Second Annual European Symposium on Algorithms (ESA'94)(Sept.1994).","DOI":"10.1007\/BFb0049428"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90188-N"},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","unstructured":"S.Irani Coloring inductive graphs on\u2010line.Proceedings of the 31st Annual Symposium on Foundations of Computer Science(FOCS) (Oct.1990)470\u2013479.","DOI":"10.1109\/FSCS.1990.89568"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.1984.1146097"},{"key":"e_1_2_1_20_2","series-title":"Lecture Notes in CS","first-page":"52","volume-title":"Proceedings of the 20th ICALP","author":"Kann V.","year":"1993"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90011-P"},{"key":"e_1_2_1_22_2","first-page":"143","article-title":"An extremal problem in recursive combinatorics","volume":"33","author":"Kierstead H. A.","year":"1981","journal-title":"Congress. Numer."},{"key":"e_1_2_1_23_2","doi-asserted-by":"crossref","unstructured":"C.LundandM.Yannakakis On the hardness of approximating minimization problems.Proceedings of the 25th ACM Symposium on Theory of Computing(STOC 1993) San Diego CA (May1993)286\u2013293.","DOI":"10.1145\/167088.167172"},{"key":"e_1_2_1_24_2","doi-asserted-by":"crossref","unstructured":"M. V.Marathe H. B.HuntIII andS. S.Ravi Efficient approximation algorithms for domatic partition and online coloring of circular\u2010arc graphs.Proceedings of the International Conference on Computing and Information (ICCI 93) Sudbury Canada (May1993)26\u201330.","DOI":"10.1109\/ICCI.1993.315408"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580444"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970401"},{"key":"e_1_2_1_27_2","first-page":"471","volume-title":"Proceedings 1987 MFCS. Lecture Notes in CS","author":"Slusarek M.","year":"1987"},{"key":"e_1_2_1_28_2","unstructured":"M.Slusarek Optimal on\u2010line coloring of circular arc graphs. Private communication (March1994)."},{"key":"e_1_2_1_29_2","volume-title":"Three\u2010dimensional Geometry & Topology","author":"Thurston W. P.","year":"1991"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.1984.1146082"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90174-3"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230250205","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230250205","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T05:55:41Z","timestamp":1737006941000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230250205"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,3]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,3]]}},"alternative-id":["10.1002\/net.3230250205"],"URL":"https:\/\/doi.org\/10.1002\/net.3230250205","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,3]]}}}