Zobrazeno 1 - 10
of 333
pro vyhledávání: '"Heggernes, Pinar"'
Chordal graphs form one of the most studied graph classes. Several graph problems that are NP-hard in general become solvable in polynomial time on chordal graphs, whereas many others remain NP-hard. For a large group of problems among the latter, ap
Externí odkaz:
http://arxiv.org/abs/1810.13326
Let $G = (V, E)$ be a connected graph with maximum degree $k\geq 3$ distinct from $K_{k+1}$. Given integers $s \geq 2$ and $p_1,\ldots,p_s\geq 0$, $G$ is said to be $(p_1, \dots, p_s)$-partitionable if there exists a partition of $V$ into sets~$V_1,\
Externí odkaz:
http://arxiv.org/abs/1803.04388
Autor:
Golovach, Petr A., Heggernes, Pinar, Konstantinidis, Athanasios L., Lima, Paloma T., Papadopoulos, Charis
Motivated by the role of triadic closures in social networks, and the importance of finding a maximum subgraph avoiding a fixed pattern, we introduce and initiate the parameterized study of the Strong F-closure problem, where F is a fixed graph. This
Externí odkaz:
http://arxiv.org/abs/1802.10386
Problems related to finding induced subgraphs satisfying given properties form one of the most studied areas within graph algorithms. Such problems have given rise to breakthrough results and led to development of new techniques both within the tradi
Externí odkaz:
http://arxiv.org/abs/1710.10979
Deciding whether a given graph has a square root is a classical problem that has been studied extensively both from graph theoretic and from algorithmic perspectives. The problem is NP-complete in general, and consequently substantial effort has been
Externí odkaz:
http://arxiv.org/abs/1703.05102
Connected Vertex Cover is one of the classical problems of computer science, already mentioned in the monograph of Garey and Johnson. Although the optimization and decision variants of finding connected vertex covers of minimum size or weight are wel
Externí odkaz:
http://arxiv.org/abs/1602.07504
Autor:
Golovach, Petr A., Heggernes, Pinar, Kanté, Mamadou Moustapha, Kratsch, Dieter, Sæther, Sigve H., Villanger, Yngve
The linear induced matching width (LMIM-width) of a graph is a width parameter defined by using the notion of branch-decompositions of a set function on ternary trees. In this paper we study output-polynomial enumeration algorithms on graphs of bound
Externí odkaz:
http://arxiv.org/abs/1509.03753
Publikováno v:
In Discrete Applied Mathematics 15 May 2020 278:3-11
