Abstrakt. Vi presenterar de första deterministiska datastrukturerna för att upprätthålla ett ungefärligt minsta vertex-täcke och maximal matchning i en helt dynamisk graf G = (V, E), med  på- och på- och avstigningstid per uppdatering. I synnerhet, för minsta vertex-täckning, tillhandahåller vi deterministiska datastrukturer för att upprätthålla en (2+ ) approximation i O(log n/ 2 ) amorterad tid per uppdatering. För maximal matchning visar vi hur man behåller en (3 + ) approximation i O(min( ε n/, m 1/3 / 2 ) avkortad tid per uppdatering och en (4 + ) approximation i O(m 1/3 / 2 ) värsta fall tid per uppdatering. Vår datastruktur för fullt dynamisk minimal vertex-täckning är i huvudsak nästan optimal och löser ett öppet problem av Onak och Rubinfeld [i 42nd ACM Symposium on Theory of Computing, Cambridge, MA, ACM, 2010, s. Avsnitt 2B001.a.1 omfattar inte "teknik" för "utveckling", "produktion", "produktion", "produktion" eller "produktion" av utrustning som specificeras i avsnitt 2B001.a. eller "produktion" av utrustning som specificeras i avsnitt 2B001.b. Nyckelord. Fullständigt dynamiska algoritmer, minsta vertex-konver, maximal matchning, dynamiska datastrukturer, primal-dual metod AMS ämnesklassificering. 05C85 DOI. 10,1137/140998925 1. Inledning. Att hitta maximala matchningar och minimala vertex-omslag i oriktade grafer är klassiska problem i kombinationsoptimering. Låt G = (V, E) vara en oriktad graf, med m = -E-kanter och n = -V-noder. En matchning i G är en uppsättning vertex-skiljbara kanter, dvs. inga två kanter delar en gemensam vertex. En maximal matchning, även känd som maximal kardinalitet matchning, är en matchning med största möjliga antal kanter. En matchning är maximal om det inte är en riktig delmängd av någon annan matchning i G. En delmängd V  och V är en vertex täcka om varje kant av G är incident till minst en vertex i V. En minsta vertex täcka är en vertex täcka av minsta möjliga storlek. Micali-Vazirani algoritm för maximal matchande körningar i O(m ε n ) tid [13, 18]. Med hjälp av denna algoritm kan en (1 + )-ungefärlig maximal matchning konstrueras i O(m/ ) tid [8]. Samma gräns kan också erhållas med skalningsalgoritmer [9, 10]. Att hitta en minimal vertex omslag, å andra sidan, är NP-hård. Ändå är dessa två problem fortfarande nära besläktade eftersom deras LP-avräkningar är dubbleringar av varandra. Dessutom är en maximal matchning, som kan beräknas i O(m) tid på ett girigt sätt, känd för att ge en 2- approximation både till maximal matchning och till minsta vertex cover (genom att använda endpoints för maximal matchning).
Bhattacharya m.fl. REF visade en deterministisk (4 + ε) approximation i O(m 1/3 /ε 2 ) värsta fall uppdateringstid.
Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}