Zobrazeno 1 - 9
of 9
pro vyhledávání: '"Banerjee, Niranka"'
Reconfiguration problems involve determining whether two given configurations can be transformed into each other under specific rules. The Token Sliding problem asks whether, given two different set of tokens on vertices of a graph $G$, we can transf
Externí odkaz:
http://arxiv.org/abs/2411.16149
Coloring a graph is a well known problem and used in many different contexts. Here we want to assign $k \geq 1$ colors to each vertex of a graph $G$ such that each edge has two different colors at each endpoint. Such a vertex-coloring, if exists, is
Externí odkaz:
http://arxiv.org/abs/2402.12705
Autor:
Banerjee, Niranka, Hoang, Duc A.
For a fixed integer $r \geq 1$, a distance-$r$ dominating set (D$r$DS) of a graph $G = (V, E)$ is a vertex subset $D \subseteq V$ such that every vertex in $V$ is within distance $r$ from some member of $D$. Given two D$r$DSs $D_s, D_t$ of $G$, the D
Externí odkaz:
http://arxiv.org/abs/2310.00241
Recent work by Elmasry et al. (STACS 2015) and Asano et al. (ISAAC 2014), reconsidered classical fundamental graph algorithms focusing on improving the space complexity. We continue this line of work focusing on space. Our first result is a simple da
Externí odkaz:
http://arxiv.org/abs/1606.04718
Publikováno v:
In Theoretical Computer Science 24 June 2020 822:1-14
Autor:
Banerjee, Niranka1 nirankab@imsc.res.in, Chakraborty, Sankardeep1 sankardeep@imsc.res.in, Raman, Venkatesh1 vraman@imsc.res.in, Satti, Srinivasa Rao2 ssrao@cse.snu.ac.kr
Publikováno v:
Theory of Computing Systems. Nov2018, Vol. 62 Issue 8, p1736-1762. 27p.
In this paper we consider two classic cut-problems, Global Min-Cut and Min k-Cut, via the lens of fault tolerant network design. In particular, given a graph G on n vertices, and a positive integer f, our objective is to compute an upper bound on the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c0fc0f3bdaa1dbbabf5b6344f41ddd34
Publikováno v:
Computing & Combinatorics: 22nd International Conference, COCOON 2016, Ho Chi Minh City, Vietnam, August 2-4, 2016, Proceedings; 2016, p119-130, 12p
Publikováno v:
Computing & Combinatorics: 21st International Conference, COCOON 2015, Beijing, China, August 4-6, 2015, Proceedings; 2015, p349-360, 12p