10 citations · 21 across the 11 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.DS2016
Tight Hardness Results for Distance and Centrality Problems in Constant Degree Graphs
Søren Dahlgaard, Jacob Evald
Finding important nodes in a graph and measuring their importance is a fundamental problem in the analysis of social networks, transportation networks, biological systems, etc. Amo…
cs.DS2016
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms
Amir Abboud, Søren Dahlgaard
The dynamic shortest paths problem on planar graphs asks us to preprocess a planar graph such that we may support insertions and deletions of edges in as well as distance q…
cs.DS2016
On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter
Søren Dahlgaard
Conditional lower bounds for dynamic graph problems has received a great deal of attention in recent years. While many results are now known for the fully-dynamic case and such bou…