.

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:

  • Highly scalable parallel search-tree algorithms 
    Abu-Khzam, Faisal N.; Mouawad, Amer A.; Jahed, Karim A. (IEEE, 2017-03-16)
    Summary form only given. We introduce the notion of a virtual topology and explore the use of search-tree indexing to achieve highly scalable parallel search-tree algorithms for NP-hard problems. Vertex Cover and Cluster ...
  • A hybrid graph representation for exact graph algorithms 
    Abu-Khzam, Faisal N.; Jahed, Karim A.; Mouawad, Amer E. (2018-04-23)
    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 number of graph modifications, such as ...
  • A hybrid graph representation for recursive backtracking algorithms 
    Abu-Khzam, Faisal N.; Langston, Micheal A.; Mouawad, Amer E.; Nolan, Clinton P. (Springer, 2017-03-20)
    Many exact algorithms for NPNP -hard graph problems adopt the old Davis-Putman branch-and-reduce paradigm. The performance of these algorithms often suffers from the increasing number of graph modifications, such as ...
  • Immersion Containment and Connectivity in Color-Critical Graphs 
    Abu-Khzam, Faisal N.; Langston, Micheal (2015-12-07)
    The relationship between graph coloring and the immersion order is considered. Vertex connectivity, edge connectivity and related issues are explored. It is shown that a t-chromatic graph G contains either an immersed Kt ...
  • An improved kernel for the undirected planar feedback vertex set problem 
    Abu-Khzam, Faisal N.; Bou Khuzam, Mazen (Springer, 2017-03-17)
    We consider the parameterized Feedback Vertex Set problem on unweighted, undirected planar graphs. We present a kernelization algorithm that takes a planar graph G and an integer k as input and either decides that (G,k) ...
  • An improved kernelization algorithm for r-Set Packing 
    Abu-Khzam, Faisal N. (2015-12-07)
    We present a reduction procedure that takes an arbitrary instance of the r -Set Packing problem and produces an equivalent instance whose number of elements is in O(kr−1), where k is the input parameter. Such parameterized ...
  • A kernelization algorithm for d-Hitting Set 
    Abu-Khzam, Faisal N. (2015-12-07)
    For a given parameterized problem, π, a kernelization algorithm is a polynomial-time pre-processing procedure that transforms an arbitrary instance of π into an equivalent one whose size depends only on the input parameter(s). ...
  • Kernelization algorithms for the vertex cover problem 
    Abu-Khzam, Faisal N.; Collins, Rebecca L.; Fellows, Micheal R.; Langston, Micheal A.; Suters, W. Henry; Symons, Christopher T. (2017-03-21)
    A variety of efficient kernelization strategies for the classic vertex cover problem are developed, implemented and compared experimentally. A new technique, termed crown reduction, is introduced and analyzed. Applications ...
  • Kernels 
    Abu-Khzam, Faisal N.; Fernau, Hernning (2017-03-20)
    The notion of a “problem kernel” plays a central role in the design of fixed-parameter algorithms. The FPT literature is rich in kernelization algorithms that exhibit fundamentally different approaches. We highlight ...
  • Linear-time algorithms for problems on planar graphs with fixed disk dimension 
    Abu-Khzam, Faisal N.; Langston, Micheal (2015-12-07)
    The disk dimension of a planar graph G is the least number k for which G embeds in the plane minus k open disks, with every vertex on the boundary of some disk. Useful properties of graphs with a given disk dimension are ...
  • Maximum common induced subgraph parameterized by vertex cover 
    Abu-Khzam, Faisal N. (2015-12-07)
    The Maximum Common Induced Subgraph problem (MCIS ) takes a pair of graphs as input and asks for a graph of maximum order that is isomorphic to an induced subgraph of each of the input graphs. The problem is NP-hard in ...
  • The maximum common subgraph problem 
    Abu-Khzam, Faisal N.; Samatova, Nagiza F.; Rizk, Mohamad A.; Langston, Micheal A. (IEEE, 2017-03-20)
    In the maximum common subgraph (MCS) problem, we are given a pair of graphs and asked to find the largest induced subgraph common to them both. With its plethora of applications, MCS is a familiar and challenging problem. ...
  • Modular-width 
    Abu-Khzam, Faisal N.; Markarian, Christine; Podipyan, Pavel (Springer, 2018-04-23)
    Many graph problems such as maximum cut, chromatic number, hamiltonian cycle, and edge dominating set are known to be fixed-parameter tractable (FPT) when parameterized by the treewidth of the input graphs, but become ...
  • The monotone circuit value problem with bounded genus is in NC 
    Abu-Khzam, Faisal N.; Makarian, Chrisitne; Li, Shouwei; Podlipyan, Pavel (Springer, 2017-03-22)
    We present an efficient parallel algorithm for the general Monotone Circuit Value Problem (MCVP) with n gates and an underlying graph of bounded genus k. Our algorithm generalizes a recent result by Limaye et al. who showed ...
  • The multi-parameterized cluster editing problem 
    Abu-Khzam, Faisal N. (Springer, 2017-03-17)
    The Cluster Editing problem seeks a transformation of a given undirected graph into a transitive graph via a minimum number of edge-edit operations. Existing algorithms often exhibit slow performance and could deliver ...
  • A new approach and faster exact methods for the maximum common subgraph problem 
    Abu-Khzam, Faisal N.; Suters, W. Henry; Zhang, Yun; Synibs, Christopher T.; Samatova, Nagiza F.; Langston, Micheal A. (Springer, 2017-03-21)
    The Maximum Common Subgraph (MCS) problem appears in many guises and in a wide variety of applications. The usual goal is to take as inputs two graphs, of order m and n, respectively, and find the largest induced subgraph ...
  • NP-hardness results for partitioning graphs into disjoint cliques and a triangle-free subgraph 
    Abu-Khzam, Faisal N.; Feghali, Carl; Muller, Haiko (2018-04-26)
    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. This problem is known to be NP-complete on ...
  • On scalable parallel recursive backtracking 
    Abu-Khzam, Faisal N.; Daudjee, Khuzaima; Mouawad, Amer E.; Nishimura, Naomi (2015-12-07)
    Supercomputers are equipped with an increasingly large number of cores to use computational power as a way of solving problems that are otherwise intractable. Unfortunately, getting serial algorithms to run in parallel to ...
  • On special-purpose hardware clusters for high-performance computational grids 
    Abu-Khzam, Faisal N.; Lehrter, Jeanne M.; Bouldin, Donald W.; Langston, Micheal A.; Peterson, Gregory D. (2017-03-22)
    Lehrter, J. M., Abu-Khzam, F. N., Bouldin, D. W., Langston, M. A., & Peterson, G. D. (2002, November). On Special-purpose Hardware Clusters for High-performance Computational Grids. In IASTED PDCS (pp. 1-5).
  • On the complexity of QoS-Aware service selection problem 
    Abu-Khzam, Faisal N.; Bazgan, Cristina; El Haddad, Joyce; Sikora, Florian (Springer, 2017-03-16)
    This paper addresses the QoS-aware service selection problem considering complex workflow patterns. More specifically, it focuses on the complexity issues of the problem. The NPNP-hardness of the problem, under various ...

Search LAUR


Advanced Search

Browse

My Account