4 papers
Online Drone Scheduling for Last-mile Delivery
Saswata Jana, Giuseppe F. Italiano, Manas Jyoti Kashyop +3
Delivering a parcel from the distribution hub to the customer's doorstep is called the \textit{last-mile delivery} step in delivery logistics. In this paper, we study a hybrid {\it…
Trade-offs in dynamic coloring for bipartite and general graphs
Manas Jyoti Kashyop, N. S. Narayanaswamy, Meghana Nasre +1
We present trade-offs in the incremental and fully dynamic settings to maintian a proper coloring. For any fully dynamic -coloring algorithm, the maximum of the update time, num…
Dynamic Data Structures for Interval Coloring
Girish Raguvir J, Manas Jyoti Kashyop, N. S. Narayanaswamy
We consider the dynamic graph coloring problem restricted to the class of interval graphs. At each update step the algorithm is presented with an interval to be colored, or a previ…
Fully dynamic approximate maximum cardinality matching in update time
Manas Jyoti Kashyop, N. S. Narayanaswamy
We present a randomized algorithm to maintain a maximal matching without 3 length augmenting paths in the fully dynamic setting. Consequently, we maintain a approximate maxim…