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.
I REF visade vi att flera naturliga grafproblem som MAXIMUM INDEPENDENT SET, MINIMI VERTEX COVER och MINIMIMINERING SET kan approximeras till inom en konstant faktor av den optimala för enhet disk grafer specificerade med hjälp av en graf teoretisk representation.
Geometry based heuristics for unit disk graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}