Abstract-The dynamiska kortaste vägar problem på plana grafer ber oss att förbehandla en planar graf G sådan att vi kan stödja insättningar och raderingar av kanter i G samt avstånd frågor mellan två noder u, v under förutsättning att begränsningen att grafen förblir planar hela tiden. Detta problem har studerats ingående i både teori och experimentella samhällen under de senaste decennierna. I den här artikeln följer vi ett nyligen och mycket aktivt arbete med att visa lägre gränser för polynomproblem baserat på populära gissningar, få de första sådana resultat för naturliga problem i planar grafer. Sådana resultat var tidigare oåtkomliga på grund av den mycket icke-planära karaktären av kända minskningar och omöjligheten att "planera prylar". Vi inför en ny ram som inspireras av tekniker från litteraturen om distansmärkningssystem och parameteriserad komplexitet. Med hjälp av vårt ramverk, visar vi att ingen algoritm för dynamiska kortaste vägar eller maximal vikt bipartite matchning i plana grafer kan stödja både uppdateringar och frågor i amortized O(n 1 2 −ε ) tid, för alla ε > 0, om inte de klassiska allpairs-kortaste-sökvägar problem kan lösas i verkligt subkubisk tid, vilket allmänt anses vara omöjligt. Vi utökar dessa resultat för att få starka lägre gränser för andra relaterade problem samt för eventuella kompromisser mellan fråge- och uppdateringstid. Intressant nog håller våra nedre gränser även i mycket restriktiva modeller där endast viktuppdateringar är tillåtna.
Dessutom har Abboud och Dahlgaard REF visat att en förbättring av denna gräns till O(n 1/2−ε ) för varje konstant ε > 0 skulle innebära en verkligt subkubisk algoritm för problemet All Pars Shortest Paths (APSP) i allmänna grafer.
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms
{'venue': '2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}