2 papers
cs.CG2017
Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
Timothy Carpenter, Fedor V. Fomin, Daniel Lokshtanov +2
We study the problem of finding a minimum-distortion embedding of the shortest path metric of an unweighted graph into a "simpler" metric . Computing such an embedding (exactly…
cs.DS2017
Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion
Timothy Carpenter, Ario Salmasi, Anastasios Sidiropoulos
The problem of routing in graphs using node-disjoint paths has received a lot of attention and a polylogarithmic approximation algorithm with constant congestion is known for undir…