Source author record

Abhiram Ranade

Abhiram Ranade appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Discrete Mathematics Distributed, Parallel, and Cluster Computing

Catalog footprint

What is connected

2works

2topics

2close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2012arXiv

Component Coloring of Proper Interval Graphs and Split Graphs

We introduce a generalization of the well known graph (vertex) coloring problem, which we call the problem of \emph{component coloring of graphs}. Given a graph, the problem is to color the vertices using minimum number of colors so that the size of each connected component of the subgraph induced by the vertices of the same color does not exceed $C$. We give a linear time algorithm for the problem on proper interval graphs. We extend this algorithm to solve two weighted versions of the problem in which vertices have integer weights. In the \emph{splittable} version the weights of vertices can be split into differently colored parts, however, the total weight of a monochromatic component cannot exceed $C$. For this problem on proper interval graphs we give a polynomial time algorithm. In the \emph{non-splittable} version the vertices cannot be split. Using the algorithm for the splittable version we give a 2-approximation algorithm for the non-splittable problem on proper interval graphs which is NP-hard. We also prove that even the unweighted version of the problem is NP-hard for split graphs.

preprint2011arXiv

Scheduling Light-trails in WDM Rings

We consider the problem of scheduling communication on optical WDM (wavelength division multiplexing) networks using the light-trails technology. We seek to design scheduling algorithms such that the given transmission requests can be scheduled using minimum number of wavelengths (optical channels). We provide algorithms and close lower bounds for two versions of the problem on an $n$ processor linear array/ring network. In the {\em stationary} version, the pattern of transmissions (given) is assumed to not change over time. For this, a simple lower bound is $c$, the congestion or the maximum total traffic required to pass through any link. We give an algorithm that schedules the transmissions using $O(c+\log{n})$ wavelengths. We also show a pattern for which $Ω(c+\log{n}/\log\log{n})$ wavelengths are needed. In the {\em on-line} version, the transmissions arrive and depart dynamically, and must be scheduled without upsetting the previously scheduled transmissions. For this case we give an on-line algorithm which has competitive ratio $Θ(\log{n})$. We show that this is optimal in the sense that every on-line algorithm must have competitive ratio $Ω(\log{n})$. We also give an algorithm that appears to do well in simulation (for the classes of traffic we consider), but which has competitive ratio between $Ω(\log^2n/\log \log{n})$ and $O(\log^2n)$. We present detailed simulations of both our algorithms.