Blocking total dominating sets via edge contractions

Autor: Felix Mann, Bernard Ries, Esther Galby

Publikováno v: Theoretical Computer Science. 877:18-35

In this paper, we study the problem of deciding whether the total domination number of a given graph G can be reduced using exactly one edge contraction (called 1 -Edge Contraction( γ t ) ). We focus on several graph classes and determine the comput

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::43b4365c103c5a02487f34cb5df859c3
https://doi.org/10.1016/j.tcs.2021.03.028

Semitotal Domination: New hardness results and a polynomial-time algorithm for graphs of bounded mim-width

Autor: Esther Galby, Andrea Munaro, Bernard Ries

Publikováno v: Munaro, A, Galby, E & Ries, B 2020, ' Semitotal Domination: New hardness results and a polynomial-time algorithm for graphs of bounded mim-width ', Theoretical Computer Science . https://doi.org/10.1016/j.tcs.2020.01.007

A semitotal dominating set of a graph G with no isolated vertex is a dominating set D of G such that every vertex in D is within distance two of another vertex in D. The minimum size γt2(G) of a semitotal dominating set of G is squeezed between the

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::200e4e1ea880d30d6554eef795d63e4f
https://doi.org/10.1016/j.tcs.2020.01.007

Parameterized Complexity of Multicut in Weighted Trees

Autor: Roohani Sharma, Esther Galby, Daniel Marx, Philipp Schepper, Prafullkumar Tale

Publikováno v: SSRN Electronic Journal.

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::4578599ce1aea51a40bc33bfb11313e9
https://doi.org/10.2139/ssrn.4236299

CPG graphs: Some structural and hardness results

Autor: Nicolas Champseix, Andrea Munaro, Bernard Ries, Esther Galby

Publikováno v: Champseix, N, Galby, E, Munaro, A & Ries, B 2021, ' CPG graphs: Some structural and hardness results ', Discrete Applied Mathematics, vol. 290, pp. 17-35 . https://doi.org/10.1016/j.dam.2020.11.018

In this paper we continue the systematic study of Contact graphs of Paths on a Grid (CPG graphs) initiated in Deniz et al. (2018). A CPG graph is a graph for which there exists a collection of pairwise interiorly disjoint paths on a grid in one-to-on

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a49eb69c71db651a1236617278bfced6
https://pure.qub.ac.uk/en/publications/cpg-graphs-some-structural-and-hardness-results(77367fa9-d7e8-4007-9567-247d37399fa3).html

Reducing the domination number of graphs via edge contractions and vertex deletions

Autor: Bernard Ries, Esther Galby, Paloma T. Lima

Publikováno v: Discrete Mathematics

In this work, we study the following problem: given a connected graph G , can we reduce the domination number of G by at least one using k edge contractions, for some fixed integer k > 0 ? We show that for k = 1 (resp. k = 2 ), the problem is NP -har

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7d584132d041e3eb0cec83f417d4922f
https://doi.org/10.1016/j.disc.2020.112169