Related references
Note: Only part of the references are listed.Dynamic algorithms via the primal-dual method
Sayan Bhattacharya et al.
INFORMATION AND COMPUTATION (2018)
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
Monika Henzinger et al.
JOURNAL OF THE ACM (2018)
DYNAMIC APPROXIMATE ALL-PAIRS SHORTEST PATHS: BREAKING THE O(mn) BARRIER AND DERANDOMIZATION
Monika Henzinger et al.
SIAM JOURNAL ON COMPUTING (2016)
Vertex cover might be hard to approximate to within 2-ε
Subhash Khot et al.
JOURNAL OF COMPUTER AND SYSTEM SCIENCES (2008)
Logarithmic lower bounds in the cell-probe model
M Patrascu et al.
SIAM JOURNAL ON COMPUTING (2006)
A new multilayered PCP and the hardness of hypergraph vertex cover
I Dinur et al.
SIAM JOURNAL ON COMPUTING (2005)