Parameterized max min feedback vertex set
Given a graph $ G $ and an integer $ k $, Max Min FVS asks whether there exists a minimal
set of vertices of size at least $ k $ whose deletion destroys all cycles. We present several …
set of vertices of size at least $ k $ whose deletion destroys all cycles. We present several …
Efficiently enumerating hitting sets of hypergraphs arising in data profiling
The transversal hypergraph problem asks to enumerate the minimal hitting sets of a
hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP'95] gave an …
hypergraph. If the solutions have bounded size, Eiter and Gottlob [SICOMP'95] gave an …
Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
M Bougeret, BMP Jansen, I Sau - arXiv preprint arXiv:2404.16695, 2024 - arxiv.org
For a fixed graph $ H $, the $ H $-SUBGRAPH HITTING problem consists in deleting the
minimum number of vertices from an input graph to obtain a graph without any occurrence of …
minimum number of vertices from an input graph to obtain a graph without any occurrence of …
A new framework for kernelization lower bounds: the case of maximum minimal vertex cover
J Araújo, M Bougeret, V Campos… - … on Parameterized and …, 2021 - drops.dagstuhl.de
Abstract In the Maximum Minimal Vertex Cover (MMVC) problem, we are given a graph G
and a positive integer k, and the objective is to decide whether G contains a minimal vertex …
and a positive integer k, and the objective is to decide whether G contains a minimal vertex …
[图书][B] Symmetric Cycles
AO Matveev - 2023 - books.google.com
This original research monograph concerns various aspects of how (based on the
decompositions of vertices of hypercube graphs with respect to their symmetric cycles) the …
decompositions of vertices of hypercube graphs with respect to their symmetric cycles) the …
Introducing lop-kernels: A framework for kernelization lower bounds
Abstract In the Maximum Minimal Vertex Cover (mmvc) problem, we are given a graph G
and a positive integer k, and the objective is to decide whether G contains a minimal vertex …
and a positive integer k, and the objective is to decide whether G contains a minimal vertex …
Pattern Recognition on Oriented Matroids: Symmetric Cycles in the Hypercube Graphs. V
AO Matveev - arXiv preprint arXiv:2106.03832, 2021 - arxiv.org
We consider decompositions of topes of the oriented matroid realizable as the arrangement
of coordinate hyperplanes in $\mathbb {R}^{2^ t} $, with respect to a distinguished symmetric …
of coordinate hyperplanes in $\mathbb {R}^{2^ t} $, with respect to a distinguished symmetric …
Algorithms and Intractability of Some NP-hard Domination Problems with Private Structure
L Dublois - 2021 - theses.hal.science
To tackle NP-hard problems, several paradigms have been developed in the last decades:
the polynomial-time approximation, the exact resolution, or the super-polynomial …
the polynomial-time approximation, the exact resolution, or the super-polynomial …
Algorithmes et Intractabilité de Certains Problèmes de Domination NP-difficiles avec Structure Privée
L Dublois - 2021 - theses.fr
Résumé Pour résoudre des problèmes NP-difficiles, plusieurs paradigmes ont été
développés durant les dernières décennies: l'approximation polynomiale, la résolution …
développés durant les dernières décennies: l'approximation polynomiale, la résolution …