On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter
From MaRDI portal
Publication:4598187
DOI10.4230/LIPIcs.ICALP.2016.48zbMath1388.68222arXiv1602.06705OpenAlexW2963365235MaRDI QIDQ4598187
Publication date: 19 December 2017
Full work available at URL: https://arxiv.org/abs/1602.06705
maximum flowmaximum cardinality matchinghardness in Pconditional lower boundsdiameter in graphspartially dynamic problems
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)
Related Items (6)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Range updates and range sum queries on multidimensional points with monoid weights ⋮ How fast can we play Tetris greedily with rectangular pieces? ⋮ Unnamed Item ⋮ Unnamed Item
This page was built for publication: On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter
