Zobrazeno 1 - 10
of 97
pro vyhledávání: '"Misra, Pranabendu"'
We introduce a new framework for the analysis of preprocessing routines for parameterized counting problems. Existing frameworks that encapsulate parameterized counting problems permit the usage of exponential (rather than polynomial) time either exp
Externí odkaz:
http://arxiv.org/abs/2308.02188
Autor:
Lokshtanov, Daniel, Misra, Pranabendu, Panolan, Fahad, Ramanujan, M. S., Saurabh, Saket, Zehavi, Meirav
The streaming model was introduced to parameterized complexity independently by Fafianie and Kratsch [MFCS14] and by Chitnis, Cormode, Hajiaghayi and Monemizadeh [SODA15]. Subsequently, it was broadened by Chitnis, Cormode, Esfandiari, Hajiaghayi and
Externí odkaz:
http://arxiv.org/abs/2308.01598
Autor:
Karrenbauer, Andreas, Wennmann, Leonie, Mehlhorn, Kurt, Misra, Pranabendu, Rinaldi, Paolo Luigi, Twelsiek, Anna, Shateranloo, Siavash Rahimi, Haqi, Alireza
Patience Sort sorts a sequence of numbers with a minimal number of queues that work according to the First-In-First-Out (FIFO) principle. More precisely, if the length of the longest descreasing subsequence of the input sequence is $L$, then Patience
Externí odkaz:
http://arxiv.org/abs/2207.02476
Publikováno v:
In Theoretical Computer Science 21 December 2024 1021
Subexponential parameterized algorithms are known for a wide range of natural problems on planar graphs, but the techniques are usually highly problem specific. The goal of this paper is to introduce a framework for obtaining $n^{O(\sqrt{k})}$ time a
Externí odkaz:
http://arxiv.org/abs/2110.15098
In the Disjoint Paths problem, the input is an undirected graph $G$ on $n$ vertices and a set of $k$ vertex pairs, $\{s_i,t_i\}_{i=1}^k$, and the task is to find $k$ pairwise vertex-disjoint paths connecting $s_i$ to $t_i$. The problem was shown to h
Externí odkaz:
http://arxiv.org/abs/2103.17041
We study the problem of fairly allocating a set of indivisible goods among $n$ agents with additive valuations. Envy-freeness up to any good (EFX) is arguably the most compelling fairness notion in this context. However, the existence of EFX allocati
Externí odkaz:
http://arxiv.org/abs/2103.01628
Autor:
Misra, Pranabendu
The study of fault-tolerant data structures for various network design problems is a prominent area of research in computer science. Likewise, the study of NP-Complete problems lies at the heart of computer science with numerous results in algorithms
Externí odkaz:
http://arxiv.org/abs/2009.06063
Let $G$ be a directed graph with $n$ vertices and $m$ edges, and let $s \in V(G)$ be a designated source vertex. We consider the problem of single source reachability (SSR) from $s$ in presence of failures of edges (or vertices). Formally, a spanning
Externí odkaz:
http://arxiv.org/abs/1904.08150
Publikováno v:
In Theoretical Computer Science 18 April 2023 954