Zobrazeno 1 - 10
of 78
pro vyhledávání: '"Tale, Prafullkumar"'
Autor:
Foucaud, Florent, Galby, Esther, Khazaliya, Liana, Li, Shaohua, Inerney, Fionn Mc, Sharma, Roohani, Tale, Prafullkumar
For a graph $G$, a subset $S\subseteq V(G)$ is called a resolving set of $G$ if, for any two vertices $u,v\in V(G)$, there exists a vertex $w\in S$ such that $d(w,u)\neq d(w,v)$. The Metric Dimension problem takes as input a graph $G$ on $n$ vertices
Externí odkaz:
http://arxiv.org/abs/2405.01344
The Path Contraction and Cycle Contraction problems take as input an undirected graph $G$ with $n$ vertices, $m$ edges and an integer $k$ and determine whether one can obtain a path or a cycle, respectively, by performing at most $k$ edge contraction
Externí odkaz:
http://arxiv.org/abs/2403.06290
Autor:
Bandopadhyay, Susobhan, Banik, Aritra, Gupta, Sushmita, Jain, Pallavi, Sahu, Abhishek, Saurabh, Saket, Tale, Prafullkumar
In the standard model of fair allocation of resources to agents, every agent has some utility for every resource, and the goal is to assign resources to agents so that the agents' welfare is maximized. Motivated by job scheduling, interest in this pr
Externí odkaz:
http://arxiv.org/abs/2403.04265
Autor:
Tale, Prafullkumar
Consider the Telephone Broadcast problem in which an input is a connected graph $G$ on $n$ vertices, a source vertex $s \in V(G)$, and a positive integer $t$. The objective is to decide whether there is a broadcast protocol from $s$ that ensures that
Externí odkaz:
http://arxiv.org/abs/2403.03501
We investigate fine-grained algorithmic aspects of identification problems in graphs and set systems, with a focus on Locating-Dominating Set and Test Cover. We prove the (tight) conditional lower bounds for these problems when parameterized by treew
Externí odkaz:
http://arxiv.org/abs/2402.08346
In this work, we initiate the complexity study of Biclique Contraction and Balanced Biclique Contraction. In these problems, given as input a graph G and an integer k, the objective is to determine whether one can contract at most k edges in G to obt
Externí odkaz:
http://arxiv.org/abs/2307.10607
Autor:
Foucaud, Florent, Galby, Esther, Khazaliya, Liana, Li, Shaohua, Inerney, Fionn Mc, Sharma, Roohani, Tale, Prafullkumar
Treewidth (tw) is an important parameter that, when bounded, yields tractability for many problems. For example, graph problems expressible in Monadic Second Order (MSO) logic and QUANTIFIED SAT or, more generally, QUANTIFIED CSP, are FPT parameteriz
Externí odkaz:
http://arxiv.org/abs/2307.08149
The game of rendezvous with adversaries is a game on a graph played by two players: Facilitator and Divider. Facilitator has two agents and Divider has a team of $k \ge 1$ agents. While the initial positions of Facilitator's agents are fixed, Divider
Externí odkaz:
http://arxiv.org/abs/2210.02582
The leafage of a chordal graph G is the minimum integer l such that G can be realized as an intersection graph of subtrees of a tree with l leaves. We consider structural parameterization by the leafage of classical domination and cut problems on cho
Externí odkaz:
http://arxiv.org/abs/2208.02850
For a graph $G$, a subset $S \subseteq V(G)$ is called a \emph{resolving set} if for any two vertices $u,v \in V(G)$, there exists a vertex $w \in S$ such that $d(w,u) \neq d(w,v)$. The {\sc Metric Dimension} problem takes as input a graph $G$ and a
Externí odkaz:
http://arxiv.org/abs/2206.15424