80 citations · 273 across the 37 of their papers we have counts for
7 papers · 1 filter
Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
Sagar Kale, Sumedh Tirodkar
We consider the maximum matching problem in the semi-streaming model formalized by Feigenbaum, Kannan, McGregor, Suri, and Zhang that is inspired by giant graphs of today. As our m…
Maximum Matching on Trees in the Online Preemptive and the Incremental Dynamic Graph Models
Sumedh Tirodkar, Sundar Vishwanathan
We study the Maximum Cardinality Matching (MCM) and the Maximum Weight Matching (MWM) problems, on trees and on some special classes of graphs, in the Online Preemptive and the Inc…
On Randomized Algorithms for Matching in the Online Preemptive Model
Ashish Chiplunkar, Sumedh Tirodkar, Sundar Vishwanathan
We investigate the power of randomized algorithms for the maximum cardinality matching (MCM) and the maximum weight matching (MWM) problems in the online preemptive model. In this…
Approximating the Regular Graphic TSP in near linear time
Ashish Chiplunkar, Sundar Vishwanathan
We present a randomized approximation algorithm for computing traveling salesperson tours in undirected regular graphs. Given an -vertex, -regular graph, the algorithm comput…
On Randomized Memoryless Algorithms for the Weighted -server Problem
Ashish Chiplunkar, Sundar Vishwanathan
The weighted -server problem is a generalization of the -server problem in which the cost of moving a server of weight through a distance is . The weigh…
Metrical Service Systems with Multiple Servers
Ashish Chiplunkar, Sundar Vishwanathan
We study the problem of metrical service systems with multiple servers (MSSMS), which generalizes two well-known problems -- the -server problem, and metrical service systems. T…