Computer Science and Engineeringhttps://repository.iitgn.ac.in/handle/123456789/4272018-07-16T12:28:36Z2018-07-16T12:28:36ZParameterized algorithms for conflict-free colorings of graphsReddy, I. Vinodhttps://repository.iitgn.ac.in/handle/123456789/37342018-06-13T12:51:59Z2018-05-01T00:00:00ZParameterized algorithms for conflict-free colorings of graphs
Reddy, I. Vinod
In this paper, we study the conflict-free coloring of graphs induced by neighborhoods. A coloring of a graph is conflict-free if every vertex has a uniquely colored vertex in its neighborhood. The conflict-free coloring problem is to color the vertices of a graph using the minimum number of colors such that the coloring is conflict-free. We consider both closed neighborhoods, where the neighborhood of a vertex includes itself, and open neighborhoods, where a vertex does not include in its neighborhood. We study the parameterized complexity of conflict-free closed neighborhood coloring and conflict-free open neighborhood coloring problems. We show that both problems are fixed-parameter tractable (FPT) when parameterized by the cluster vertex deletion number of the input graph. This generalizes the result of Gargano and Rescigno [Theoretical Computer Science, 2015] that conflict-free coloring is FPT parameterized by the vertex cover number. Also, we show that both problems admit an additive constant approximation algorithm when parameterized by the distance to threshold graphs.
We also study the complexity of the problem on special graph classes. For split graphs, we give a polynomial time algorithm for closed neighborhood conflict-free coloring problem, whereas we show that open neighborhood conflict-free coloring is NP-complete. For cographs, we show that conflict-free closed neighborhood coloring can be solved in polynomial time and conflict-free open neighborhood coloring need at most three colors. We show that interval graphs can be conflict-free colored using at most four colors.
2018-05-01T00:00:00ZGeneric Single Edge Fault Tolerant Exact Distance OracleGupta, ManojSingh, Aditihttps://repository.iitgn.ac.in/handle/123456789/36712018-05-15T10:46:18Z2018-05-01T00:00:00ZGeneric Single Edge Fault Tolerant Exact Distance Oracle
Gupta, Manoj; Singh, Aditi
Given an undirected unweighted graph G and a source set S of |S|=? sources, we want to build a data structure which can process the following query {\sc Q}(s,t,e): find the shortest distance from s to t avoiding an edge e, where s?S and t?V. When ?=n, Demetrescu, Thorup, Chowdhury and Ramachandran (SIAM Journal of Computing, 2008) designed an algorithm with O~(n2) space (O~(?) hides poly logn factor.) and O(1) query time. A natural open question is to generalize this result to any number of sources. Recently, Bil{\`o} et. al. (STACS 2018) designed a data-structure of size O~(?1/2n3/2) with the query time of O(n?????) for the above problem. We improve their result by designing a data-structure of size O~(?1/2n3/2) that can answer queries in O~(1) time. In a related problem of finding fault tolerant subgraph, Parter and Peleg (ESA 2013) showed that if detours of the {\em replacement} paths ending at a vertex t are disjoint, then the number of such paths is O(n?????). This eventually gives a bound of O(nn?????)=O(?1/2n3/2) for their problem. {\em Disjointness of detours} is a very crucial property used in the above result. We show a similar result for a subset of replacement path which \textbf{may not} be disjoint. This result is the crux of our paper and may be of independent interest.?
2018-05-01T00:00:00ZFully dynamic maximal matching in O(log N) update timeBaswana, SurenderGupta, ManojSen, Sandeephttps://repository.iitgn.ac.in/handle/123456789/36552018-05-15T10:39:50Z2018-01-01T00:00:00ZFully dynamic maximal matching in O(log N) update time
Baswana, Surender; Gupta, Manoj; Sen, Sandeep
We present an algorithm for maintaining a maximal matching in a graph under
addition and deletion of edges. Our algorithm is randomized and it takes expected amortized O(log n)
time for each edge update, where n is the number of vertices in the graph. Moreover, for any sequence
of t edge updates, the total time taken by the algorithm is O(tlog n + n log2 n) with high probability
2018-01-01T00:00:00ZSimple dynamic algorithms for Maximal Independent Set and other problemsGupta, ManojKhan, Shahbazhttps://repository.iitgn.ac.in/handle/123456789/36262018-04-18T12:11:17Z2018-04-01T00:00:00ZSimple dynamic algorithms for Maximal Independent Set and other problems
Gupta, Manoj; Khan, Shahbaz
2018-04-01T00:00:00Z