Zobrazeno 1 - 10
of 111
pro vyhledávání: '"Monnot, Jerome"'
We study the following problem: for given integers $d,k$ and graph $G$, can we obtain a graph with diameter $d$ via at most $k$ edge deletions ? We determine the computational complexity of this and related problems for different values of $d$.
Externí odkaz:
http://arxiv.org/abs/2010.00273
A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of diamond-free graphs, from both structural and algorit
Externí odkaz:
http://arxiv.org/abs/2006.13822
Autor:
Casel, Katrin, Fernau, Henning, Khosravian Ghadikolaei, Mehdi, Monnot, Jérôme, Sikora, Florian
Publikováno v:
In Discrete Applied Mathematics 15 December 2023 340:183-201
Publikováno v:
In Theoretical Computer Science 9 January 2023 940 Part A:97-111
Optimization problems consist of either maximizing or minimizing an objective function. Instead of looking for a maximum solution (resp. minimum solution), one can find a minimum maximal solution (resp. maximum minimal solution). Such "flipping" of t
Externí odkaz:
http://arxiv.org/abs/1811.02599
The maximum independent set problem is known to be NP-hard in the class of subcubic graphs, i.e. graphs of vertex degree at most 3. We present a polynomial-time solution in a subclass of subcubic graphs generalizing several previously known results.
Externí odkaz:
http://arxiv.org/abs/1810.10940
Autor:
Casel, Katrin, Fernau, Henning, Ghadikolaei, Mehdi Khosravian, Monnot, Jérôme, Sikora, Florian
We consider extension variants of the classical graph problems Vertex Cover and Independent Set. Given a graph $G=(V,E)$ and a vertex set $U \subseteq V$, it is asked if there exists a minimal vertex cover (resp.\ maximal independent set) $S$ with $U
Externí odkaz:
http://arxiv.org/abs/1810.04629
Autor:
Casel, Katrin, Fernau, Henning, Ghadikolaei, Mehdi Khosravian, Monnot, Jérôme, Sikora, Florian
The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating minimal dominating sets of a graph $G=(V,E)$, one usually arrives at the
Externí odkaz:
http://arxiv.org/abs/1810.04553
Selecting a set of alternatives based on the preferences of agents is an important problem in committee selection and beyond. Among the various criteria put forth for the desirability of a committee, Pareto optimality is a minimal and important requi
Externí odkaz:
http://arxiv.org/abs/1803.06644
Autor:
Casel, Katrin, Fernau, Henning, Khosravian Ghadikolaei, Mehdi, Monnot, Jérôme, Sikora, Florian
Publikováno v:
In Theoretical Computer Science 15 February 2022 904:48-65