.

Browsing School of Arts and Sciences by Author "Abu-Khzam, Faisal N."

LAUR Repository

Browsing School of Arts and Sciences by Author "Abu-Khzam, Faisal N."

Sort by: Order: Results:

  • On the complexity of various parameterizations of common induced subgraph isomorphism 
    Abu-Khzam, Faisal N.; Bonnet, Edouard; Sikora, Florian (Springer, 2017-03-16)
    Maximum Common Induced Subgraph (henceforth MCIS) is among the most studied classical NPNP -hard problems. MCIS remains NPNP -hard on many graph classes including bipartite graphs, planar graphs and k-trees. Little is ...
  • On the parameterized complexity of dynamic problems 
    Abu-Khzam, Faisal N.; Egan, Judith; Fellows, Michael R.; Rosamond, Frances A.; Shaw, Peter (2016-11-08)
    In a dynamic version of a (base) problem X it is assumed that some solution to an instance of X is no longer feasible due to changes made to the original instance, and it is required that a new feasible solution be obtained ...
  • On the parameterized parallel complexity and the vertex cover problem 
    Abu-Khzam, Faisal N.; Li, Shouwei; Markarian, Chrisitne; Meyer auf der Heide, Friedhelm; Podipyan, PAvel (Springer, 2018-04-24)
    Efficiently parallelizable parameterized problems have been classified as being either in the class FPP (fixed-parameter parallelizable) or the class PNC (parameterized analog of NC), which contains FPP as a subclass. In ...
  • On the relative efficiency of maximal clique enumeration algorithms, with application to high-throughput computational biology 
    Abu-Khzam, Faisal N.; Baldwin, Nicole E.; Langston, Micheal A.; Samatova, Nagiza F. (2018-04-24)
    The efficient enumeration of maximal cliques has applications in microarray analysis and a number of other foundational problems of computational biology. In this paper, we analyze and test existing maximal clique enumeration ...
  • Parameterized Algorithms for Finding Small Independent Dominating Sets in Planar Graphs 
    Abu-Khzam, Faisal N.; Fernau, Henning (2016-11-09)
  • Partitioning a graph into degenerate subgraphs 
    Abu-Khzam, Faisal N.; Feghali, Carl; Heggernes, Pinar (2018-04-26)
    Let G = (V, E) be a connected graph with maximum degree k ≥ 3 distinct from Kk+1. Given integers s ≥ 2 and p1, . . . , ps ≥ 0, G is said to be (p1, . . . , ps)-partitionable if there exists a partition of V into sets V1, ...
  • Partitioning a graph into disjoint cliques and a triangle-free graph 
    Abu-Khzam, Faisal N.; Feghali, Carl; Muller, Haiko (2015-12-07)
    A graph G=(V,E) is partitionable if there exists a partition {A,B} of V such that A induces a disjoint union of cliques (i.e. , G[A] is P3-free) and B induces a triangle-free graph (i.e. , G[B] is K3-free). In this ...
  • Pseudo-Kernelization 
    Abu-Khzam, Faisal N. (2015-12-07)
    Pseudo-kernelization is introduced in this paper as a new strategy for improving fixed-parameter algorithms. This new technique works for bounded search tree algorithms by identifying favorable branching conditions whose ...
  • A quadratic kernel for 3-set packing 
    Abu-Khzam, Faisal N. (Springer, 2017-03-20)
    We present a reduction procedure that takes an arbitrary instance of the 3-Set Packing problem and produces an equivalent instance whose number of elements is bounded by a quadratic function of the input parameter. Such ...
  • A ratio Tauberian theorem 
    Abu-Khzam, Faisal N. (Amercian University of Beirut, 2018-04-24)
    Let f be a given function and Tf some integral transform of it. The question of deducing the asymptotic behavior of - from that of Tf is classical and has received much attention. More recently the question of deducing the ...
  • Scalable parallel algorithms for difficult combinatorial problems 
    Abu-Khzam, Faisal N.; Langston, Micheal A.; Shanbhag, Pushkar (2018-04-24)
    A novel combination of emergent algorithmic methods, powerful computational platforms and supporting infrastructure is described. These complementary tools and technologies are used to launch systematic attacks on combinatorial ...
  • Scalable Parallel Algorithms for FPT Problems 
    Abu-Khzam, Faisal N.; Langston, Micheal; Shanbhag, Pushkar; Symons, Christopher (2015-12-07)
    Algorithmic methods based on the theory of fixed-parameter tractability are combined with powerful computational platforms to launch systematic attacks on combinatorial problems of significance. As a case study, optimal ...
  • Turbo-charging dominating set with an FPT subroutine 
    Abu-Khzam, Faisal N.; Cai, Shaowei; Egan, Judith; Shaw, Peter; Wang, Kai (Springer, 2018-04-24)
    Turbo-charging is a recent algorithmic technique that is based on the fixed-parameter tractability of the dynamic versions of some problems as a way to improve heuristics. We demonstrate the effectiveness of this technique ...
  • Using out-of-core techniques to produce exact solutions to the maximum clique problem on extremely large graphs 
    Abu-Khzam, Faisal N.; Rogers, Gray L.; Perkins, Andy D.; Phillips, Charles A.; Eblen, John D.; Langston, Micheal A. (IEEE, 2017-03-20)
    Practical methods are presented for computing exact solutions to the maximum clique problem on graphs that are too large to fit within core memory. These methods use a combination of in-core and out-of-core techniques, ...

Search LAUR


Advanced Search

Browse

My Account