En diskkurva är skärningskurvan för en uppsättning diskar med godtyckliga diametrar i planet. För det fall disk representation ges, presenterar vi polynom-tids approximation system (PTAS) för maximal vikt oberoende set problem (välja isär diskar av maximal total vikt) och för minimal vikt vertex cover problem i disk grafer. Dessa är de första kända PTAS för N P-hårda optimeringsproblem på diskgrafer. De bygger på en ny rekursiv indelning av planet som gör det möjligt att tillämpa en skiftande strategi på olika nivåer samtidigt, så att en dynamisk programmeringsmetod blir möjlig. De PTAS för disk grafer representerar en gemensam generalisering av tidigare resultat för planar grafer och enhet disk grafer. De kan utvidgas till skärningsdiagram över andra "diskliknande" geometriska objekt (såsom kvadrater eller regelbundna polygoner), även i högre dimensioner. Nyckelord. oberoende uppsättning, vertex täcka, flytta strategi, disk graf AMS ämnesklassificeringar. 68Q25, 68R10 DOI. 10,1137/S0097539702402676 1. Inledning. Intersektionsgrafer är grafer vars hörn representeras av satser så att två hörn är intilliggande om och endast om motsvarande uppsättningar har en icke-tom skärningspunkt. De har studerats av många författare [12, 6, 24]. Vi är intresserade av approximationsalgoritmer för N P-hårda optimeringsproblem på skärningsdiagram över geometriska objekt, särskilt approximationsalgoritmer för oberoende set och vertex cover. Två framträdande tillämpningar av grafer för geometrisk skärningspunkt är frekvenstilldelning i cellulära nätverk [13, 22] och kartmärkning [1]. Målet med den maximala vikten oberoende uppsättning problem (MWIS) är att beräkna, för en given uppsättning geometriska objekt med vissa vikter, en delmängd av osammanhängande (icke-överlappande) objekt med maximal totalvikt. Målet med minimal vikt vertex täcka problem (MWVC) är att beräkna en delmängd av de givna objekten med minsta total vikt sådan att, för två skär objekt, minst ett av objekten ingår i delmängd. MIS och MVC hänvisar till de oviktade versionerna av dessa problem. Vi får polynom-tids approximationssystem för MWIS och MWVC i skärningsdiagram över diskar, kvadrater eller andra "diskliknande" objekt, även i högre dimensioner.
I kombination med en dynamisk programmeringsstrategi ger den skiftande strategin också en PTAS för Maximum Independent Set problem på Disk Graphs med godtyckliga radi REF.
Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}