6 citations · 24 across the 32 of their papers we have counts for
8 papers · 1 filter
Kernelization for Graph Packing Problems via Rainbow Matching
Stéphane Bessy, Marin Bougeret, Dimitrios M. Thilikos +1
We introduce a new kernelization tool, called rainbow matching technique}, that is appropriate for the design of polynomial kernels for packing problems and their hitting counterpa…
FPT algorithms for packing -safe spanning rooted sub(di)graphs
Stéphane Bessy, Florian Hörsch, Ana Karolinna Maia +2
We study three problems introduced by Bang-Jensen and Yeo [Theor. Comput. Sci. 2015] and by Bang-Jensen, Havet, and Yeo [Discret. Appl. Math. 2016] about finding disjoint "balanced…
Width Parameterizations for Knot-free Vertex Deletion on Digraphs
Stéphane Bessy, Marin Bougeret, Alan D. A. Carneiro +2
A knot in a directed graph is a strongly connected subgraph of with at least two vertices, such that no vertex in is an in-neighbor of a vertex in $V(G)\setminus…
Degree-constrained 2-partitions of graphs
Joergen Bang-Jensen, Stéphane Bessy
A -partition of a graph is a vertex-partition of satisfying that for . We determine, for all positive integers…
Triangle packing in (sparse) tournaments: approximation and kernelization
Stéphane Bessy, Marin Bougeret, Jocelyn Thiebaut
Given a tournament T and a positive integer k, the C_3-Pakcing-T problem asks if there exists a least k (vertex-)disjoint directed 3-cycles in T. This is the dual problem in tourna…
On independent set on B1-EPG graphs
Marin Bougeret, Stephane Bessy, Daniel Gonçalves +1
In this paper we consider the Maximum Independent Set problem (MIS) on -EPG graphs. EPG (for Edge intersection graphs of Paths on a Grid) was introduced in ~\cite{edgeintersin…