4 citations · 16 across the 22 of their papers we have counts for
5 papers · 1 filter
On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism
Faisal N. Abu-Khzam, Édouard Bonnet, Florian Sikora
In the Maximum Common Induced Subgraph problem (henceforth MCIS), given two graphs and , one looks for a graph with the maximum number of vertices being both an induced…
Data Reductions and Combinatorial Bounds for Improved Approximation Algorithms
Faisal N. Abu-Khzam, Cristina Bazgan, Morgan Chopin +1
Kernelization algorithms in the context of Parameterized Complexity are often based on a combination of reduction rules and combinatorial insights. We will expose in this paper a s…
A Hybrid Graph Representation for Exact Graph Algorithms
Faisal N. Abu-Khzam, Karim A. Jahed, Amer E. Mouawad
Many exact search algorithms for NP-hard graph problems adopt the old Davis-Putman branch-and-reduce paradigm. The performance of these algorithms often suffers from the increasing…
NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph
Carl Feghali, Faisal N. Abu-Khzam, Haiko Müller
This paper investigates the computational complexity of deciding whether the vertices of a graph can be partitioned into a disjoint union of cliques and a triangle-free subgraph. T…
Partitioning a Graph into Disjoint Cliques and a Triangle-free Graph
Faisal N. Abu-Khzam, Carl Feghali, Haiko Müller
A graph is \emph{partitionable} if there exists a partition of such that induces a disjoint union of cliques and induces a triangle-free graph.…