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…