5 papers
Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM
Vignesh Manoharan, Vijaya Ramachandran
The distance sensitivity oracle (DSO) problem asks us to preprocess a given graph in order to answer queries of the form , which denotes the shortest path dista…
Distributed Distance Sensitivity Oracles
Vignesh Manoharan, Vijaya Ramachandran
We present results for the distance sensitivity oracle (DSO) problem, where one needs to preprocess a given directed weighted graph in order to answer queries about the s…
Improved Approximation Bounds for Minimum Weight Cycle in the CONGEST Model
Vignesh Manoharan, Vijaya Ramachandran
Minimum Weight Cycle (MWC) is the problem of finding a simple cycle of minimum weight in a graph . This is a fundamental graph problem with classical sequential algorithms…
Near Optimal Bounds for Replacement Paths and Related Problems in the CONGEST Model
Vignesh Manoharan, Vijaya Ramachandran
We present several results in the CONGEST model on round complexity for Replacement Paths (RPaths), Minimum Weight Cycle (MWC), and All Nodes Shortest Cycles (ANSC). We study these…
AUPCR Maximizing Matchings : Towards a Pragmatic Notion of Optimality for One-Sided Preference Matchings
Girish Raguvir J, Rahul Ramesh, Sachin Sridhar +1
We consider the problem of computing a matching in a bipartite graph in the presence of one-sided preferences. There are several well studied notions of optimality which include pa…