Enhet disk grafer är skärnings grafer av cirklar av enhet radie i planet. Vi presenterar enkla och bevisligen bra heuristiker för ett antal klassiska NP-hårda optimeringsproblem på enhetsdiskgrafer. De problem som beaktas inkluderar maximal oberoende uppsättning, minsta vertex cover, minimal färgning och minsta dominerande uppsättning. Vi presenterar också en on-line färg heuristic som uppnår ett konkurrenskraftigt förhållande på 6 för enhet disk grafer. Våra heuristiker behöver inte en geometrisk representation av enhetsdiskgrafer. Geometriska representationer används endast för att fastställa prestandagarantier för heuristikerna. Flera av våra approximationsalgoritmer kan utvidgas till skärningsgrafer av cirklar av godtyckliga radier i planet, skärningsgrafer av regelbundna polygoner, och skärningsgrafer av högre dimensionella reguljära objekt.
Marathe m.fl. REF studerade flera approximativa resultat för enhetsdiskgrafer, såsom metoder för maximal oberoende uppsättning, minsta vertex omslag, minsta färgning och minsta dominerande uppsättning.
Geometry based heuristics for unit disk graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}