Zobrazeno 1 - 10
of 170
pro vyhledávání: '"Ramanujan, M. S."'
In many real-world routing problems, decision makers must optimise over sparse graphs such as transportation networks with non-metric costs on the edges that do not obey the triangle inequality. Motivated by finding a sufficiently long running route
Externí odkaz:
http://arxiv.org/abs/2410.10440
Over the last decade, extensive research has been conducted on the algorithmic aspects of designing single-elimination (SE) tournaments. Addressing natural questions of algorithmic tractability, we identify key properties of input instances that enab
Externí odkaz:
http://arxiv.org/abs/2408.15068
In this paper, we study the Eulerian Strong Component Arc Deletion problem, where the input is a directed multigraph and the goal is to delete the minimum number of arcs to ensure every strongly connected component of the resulting digraph is Euleria
Externí odkaz:
http://arxiv.org/abs/2408.13819
We study the parameterized complexity of a generalization of the coordinated motion planning problem on graphs, where the goal is to route a specified subset of a given set of $k$ robots to their destinations with the aim of minimizing the total ener
Externí odkaz:
http://arxiv.org/abs/2404.15950
Single-elimination (SE) tournaments are a popular format used in competitive environments and decision making. Algorithms for SE tournament manipulation have been an active topic of research in recent years. In this paper, we initiate the algorithmic
Externí odkaz:
http://arxiv.org/abs/2402.06538
Given a simple connected undirected graph G = (V, E), a set X \subseteq V(G), and integers k and p, STEINER SUBGRAPH EXTENSION problem asks if there exists a set S \supseteq X with at most k vertices such that G[S] is p-edge-connected. This is a natu
Externí odkaz:
http://arxiv.org/abs/2311.02708
For numerous graph problems in the realm of parameterized algorithms, using the size of a smallest deletion set (called a modulator) into well-understood graph families as parameterization has led to a long and successful line of research. Recently,
Externí odkaz:
http://arxiv.org/abs/2310.03469
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
We study the CONNECTED \eta-TREEDEPTH DELETION problem where the input instance is an undireted graph G = (V, E) and an integer k. The objective is to decide if G has a set S \subseteq V(G) of at most k vertices such that G - S has treedepth at most
Externí odkaz:
http://arxiv.org/abs/2212.00418
Majority illusion occurs in a social network when the majority of the network nodes belong to a certain type but each node's neighbours mostly belong to a different type, therefore creating the wrong perception, i.e., the illusion, that the majority
Externí odkaz:
http://arxiv.org/abs/2205.02056