Zobrazeno 1 - 10
of 218
pro vyhledávání: '"Liedloff, Mathieu"'
The question to enumerate all inclusion-minimal connected dominating sets in a graph of order $n$ in time significantly less than $2^n$ is an open question that was asked in many places. We answer this question affirmatively, by providing an enumerat
Externí odkaz:
http://arxiv.org/abs/2205.00086
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Garnero, Valentin, Junosza-Szaniawski, Konstanty, Liedloff, Mathieu, Montealegre, Pedro, Rzążewski, Paweł
In this paper we consider a variation of a recoloring problem, called the Color-Fixing. Let us have some non-proper $r$-coloring $\varphi$ of a graph $G$. We investigate the problem of finding a proper $r$-coloring of $G$, which is "the most similar"
Externí odkaz:
http://arxiv.org/abs/1607.06911
Autor:
Bazgan, Cristina, Brankovic, Ljiljana, Casel, Katrin, Fernau, Henning, Jansen, Klaus, Lampis, Michael, Liedloff, Mathieu, Monnot, Jérôme, Paschos, Vangelis Th.
In this paper we study combinatorial and algorithmic resp. complexity questions of upper domination, i.e., the maximum cardinality of a minimal dominating set in a graph. We give a full classification of the related maximisation and minimisation prob
Externí odkaz:
http://arxiv.org/abs/1506.07260
In this paper we give upper bounds on the number of minimal separators and potential maximal cliques of graphs w.r.t. two graph parameters, namely vertex cover ($\operatorname{vc}$) and modular width ($\operatorname{mw}$). We prove that for any graph
Externí odkaz:
http://arxiv.org/abs/1404.3882
After the number of vertices, Vertex Cover is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the Vertex C
Externí odkaz:
http://arxiv.org/abs/1305.0433
Publikováno v:
In Theoretical Computer Science 6 September 2019 783:41-52
Publikováno v:
In Discrete Applied Mathematics 31 July 2019 265:69-85
Publikováno v:
Proc. AAAI'12, pp. 750-756 (AAAI Press 2012)
Inferring probabilistic networks from data is a notoriously difficult task. Under various goodness-of-fit measures, finding an optimal network is NP-hard, even if restricted to polytrees of bounded in-degree. Polynomial-time algorithms are known only
Externí odkaz:
http://arxiv.org/abs/1208.1692
Autor:
Gaspers, Serge, Liedloff, Mathieu
An independent dominating set D of a graph G = (V,E) is a subset of vertices such that every vertex in V \ D has at least one neighbor in D and D is an independent set, i.e. no two vertices of D are adjacent in G. Finding a minimum independent domina
Externí odkaz:
http://arxiv.org/abs/1009.1381