48 citations · 69 across the 9 of their papers we have counts for
Showing 2014Show all
3 papers · 1 filter
cs.CC2014★ 2 cited
Optimal Hub Labeling is NP-complete
Mathias Weller
Distance labeling is a preprocessing technique introduced by Peleg [Journal of Graph Theory, 33(3)] to speed up distance queries in large networks. Herein, each vertex receives a (…
cs.DS2014
A Polynomial-time Algorithm for Outerplanar Diameter Improvement
Nathann Cohen, Daniel Gonçalves, Eun Jung Kim +4
The Outerplanar Diameter Improvement problem asks, given a graph and an integer , whether it is possible to add edges to in a way that the resulting graph is outerplanar…
cs.DM2014★ 48 cited
Interval scheduling and colorful independent sets
René van Bevern, Matthias Mnich, Rolf Niedermeier +1
Numerous applications in scheduling, such as resource allocation or steel manufacturing, can be modeled using the NP-hard Independent Set problem (given an undirected graph and an…