Zobrazeno 1 - 10
of 369
pro vyhledávání: '"Zehavi, Meirav"'
The parameterized analysis of graph modification problems represents the most extensively studied area within Parameterized Complexity. Given a graph $G$ and an integer $k\in\mathbb{N}$ as input, the goal is to determine whether we can perform at mos
Externí odkaz:
http://arxiv.org/abs/2411.13171
In this article we show that Maximum Partial List H-Coloring is polynomial-time solvable on P_5-free graphs for every fixed graph H. In particular, this implies that Maximum k-Colorable Subgraph is polynomial-time solvable on P_5-free graphs. This an
Externí odkaz:
http://arxiv.org/abs/2410.21569
Autor:
Da Lozzo, Giordano, Ganian, Robert, Gupta, Siddharth, Mohar, Bojan, Ordyniak, Sebastian, Zehavi, Meirav
We study Clustered Planarity with Linear Saturators, which is the problem of augmenting an $n$-vertex planar graph whose vertices are partitioned into independent sets (called clusters) with paths - one for each cluster - that connect all the vertice
Externí odkaz:
http://arxiv.org/abs/2409.19410
The class of graph deletion problems has been extensively studied in theoretical computer science, particularly in the field of parameterized complexity. Recently, a new notion of graph deletion problems was introduced, called deletion to scattered g
Externí odkaz:
http://arxiv.org/abs/2409.14209
For a finite set $\mathcal{F}$ of graphs, the $\mathcal{F}$-Hitting problem aims to compute, for a given graph $G$ (taken from some graph class $\mathcal{G}$) of $n$ vertices (and $m$ edges) and a parameter $k\in\mathbb{N}$, a set $S$ of vertices in
Externí odkaz:
http://arxiv.org/abs/2409.04786
In a disk graph, every vertex corresponds to a disk in $\mathbb{R}^2$ and two vertices are connected by an edge whenever the two corresponding disks intersect. Disk graphs form an important class of geometric intersection graphs, which generalizes bo
Externí odkaz:
http://arxiv.org/abs/2407.09356
We propose a novel clustering model encompassing two well-known clustering models: k-center clustering and k-median clustering. In the Hybrid k-Clusetring problem, given a set P of points in R^d, an integer k, and a non-negative real r, our objective
Externí odkaz:
http://arxiv.org/abs/2407.08295
Challenge the champ tournaments are one of the simplest forms of competition, where a (initially selected) champ is repeatedly challenged by other players. If a player beats the champ, then that player is considered the new (current) champ. Each play
Externí odkaz:
http://arxiv.org/abs/2403.17587
We initiate the study of the parameterized complexity of the {\sc Collective Graph Exploration} ({\sc CGE}) problem. In {\sc CGE}, the input consists of an undirected connected graph $G$ and a collection of $k$ robots, initially placed at the same ve
Externí odkaz:
http://arxiv.org/abs/2310.05480
Over the past decade, we witness an increasing amount of interest in the design of exact exponential-time and parameterized algorithms for problems in Graph Drawing. Unfortunately, we still lack knowledge of general methods to develop such algorithms
Externí odkaz:
http://arxiv.org/abs/2310.05471