206 citations · 303 across the 29 of their papers we have counts for
Showing 2018Show all
3 papers · 1 filter
cs.DS2018
Almost Optimal Distance Oracles for Planar Graphs
Panagiotis Charalampopoulos, Paweł Gawrychowski, Shay Mozes +1
We present new tradeoffs between space and query-time for exact distance oracles in directed weighted planar graphs. These tradeoffs are almost optimal in the sense that they are w…
cs.DS2018
Near-Optimal Distance Emulator for Planar Graphs
Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes +1
Given a graph and a set of terminals , a \emph{distance emulator} of is another graph (not necessarily a subgraph of ) containing , such that all the pairwise…
cs.DS2018
A Faster FPTAS for #Knapsack
Paweł Gawrychowski, Liran Markin, Oren Weimann
Given a set of non-negative integer weights and an integer , the #Knapsack problem asks to count the number of distinct subsets of whose total weig…