Recent Publications by Faisal N. Abu-Khzam


Journal articles

  • On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism.
    (joint work with E. Bonnet and F. Sikora)
    Theoretical Computer Science, 2017. Accepted for publication.

  • On the Complexity of Multi-Parameterized Cluster Editing
    Journal of Discrete Algorithms (2017), http://dx.doi.org/10.1016/j.jda.2017.07.003

  • Enumerating Minimal Dominating Sets in Chordal Graphs
    (joint work with P. Heggernes)
    Information Processing Letters, volume 116(12), pages 739-743, 2016.

  • Data Reductions and Combinatorial Bounds for Improved Approximation Algorithms
    (joint work with C. Bazgan, M. Chopin and H. Fernau)
    Journal of Computer and System Sciences, volume 82, pages 503-520, 2016.

  • On the Parameterized Complexity of Dynamic Problems
    (joint work with J. Egan, M. R. Fellows, F. A. Rosamond and P. Shaw)
    Theoretical Computer Science, volume 607(3), pages 426-434, 2015.

  • On Scalable Parallel Recursive Backtracking
    (joint work with K. Daudjee, A. E. Mouawad and N. Nishimura)
    Journal of Parallel and Distributed Computing, volume 84, pages 65-75, 2015.

  • Partitioning a Graph into Disjoint Cliques and a Triangle-free Graph
    (joint work with C. Feghali and H. Muller)
    Discrete Applied Mathematics, 190-191, pages 1-12, 2015.

  • Maximum Common Induced Subgraph Parameterized by Vertex Cover
    Information Processing Letters, volume 114, number 3, pages 99-103, 2014.

  • Immersion Containment and Connectivity in Color-Critical Graphs
    (joint work with M. A. Langston)
    Discrete Mathematics and Theoretical Computer Science , volume 14, number 2, pages 155-164, 2012.

  • An Exact Algorithm for Connected Red-Blue Dominating Set
    (joint work with A. Mouawad and M. Liedloff)
    Journal of Discrete Algorithms, volume 9, number 3, pages 252-262, 2011.

  • Charge and Reduce: A Fixed-Parameter Algorithm for String-to-String Correction.
    (joint work with H. Fernau, M. A. Langston, U. Stege and S. Lee-Cultura)
    Discrete Optimization, volume 8, number 1, pages 41-49, 2011.

  • A Kernelization Algorithm for r-Set Packing
    Information Processing Letters, volume 110, number 16, pages 621-624, 2010.

  • A Kernelization Algorithm for d-Hitting Set
    Journal of Computer and System Sciences, volume 76, number 7, pages 524-531, 2010.

  • A Bounded Search Tree Algorithm for Parameterized Face Cover
    (joint work with H. Fernau and M. A. Langston)
    Journal of Discrete Algorithms, Volume 6, Issue 4, pages 541-552, 2008.

  • Pseudo-Kernelization: A Branch-then-Reduce Approach for FPT Problems
    Theory of Computing Systems, volume 41, number 3, pages 399-410, 2007.

  • Crown Structures for Vertex Cover Kernelization
    (joint work with M. R. Fellows, M. A. Langston and W. H. Suters)
    Theory of Computing Systems, volume 41, number 3, pages 411-430, 2007.

  • Linear-time algorithms for problems on planar graphs with fixed disk dimension
    (joint work with Michael A. Langston)
    Information Processing Letters, volume 101, number 1, pages 36-40, 2007.

  • Parameterized Algorithms for Finding Small Independent Dominating Sets in Planar Graphs
    (joint work Henning Fernau)
    Electronic Notes in Discrete Mathematics, volume 25, pages 1-6, 2006.
    (Special issue of the Cologne-Twente Workshop on Graphs and Combinatorial Optimization, June 2006.)

  • Scalable Parallel Algorithms for FPT Problems
    (joint work with M. A. Langston, P. Shanbhag and C. T. Symons)
    Algorithmica, volume 45, pages 269-284, 2006.

    Conference proceedings

  • Modular-width: An Auxiliary Parameter for Parameterized Parallel Complexity
    (joint work with S. Li, C. Markarian, F. Meyer auf der Heide and P. Podlipyan)
    in Proceedings of the 11th International Frontiers of Algorithmics Workshop (FAW 2017).
    Accepted for publication.

  • Turbo-charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis
    (joint work with Shaowei Cai, Judith Egan, Peter Shaw and Kai Wang)
    in Proceedings of the 14th annual conference on Theory and Applications of Models of Computation (TAMC 2017).
    Accepted for publication.

  • Building Clusters with Lower-bounded Sizes
    (joint work with C. Bazgan, K. Casel and H. Fernau)
    in Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC 2016).
    Accepted for publication.

  • On the Parameterized Parallel Complexity and the Vertex Cover Problem
    (joint work with S. Li, C. Markarian, F. Meyer auf der Heide and P. Podlipyan)
    in Proceedings of the 10th International Conference on Combinatorial Optimization and Applications (COCOA 2016).
    Accepted for publication.

  • The Monotone Circuit Value Problem with Bounded Genus is in NC
    (joint work with S. Li, C. Markarian, F. Meyer auf der Heide and P. Podlipyan)
    in Proceedings of the 22nd International Computing and Combinatorics Conference (COCOON 2016).
    Accepted for publication.

  • On the Complexity of QoS-aware Service Selection Problem
    (joint work with C. Bazgan, J. El-Haddad and F. Sikora)
    in Proceedings of the 13th International Conference on Service Oriented Computing (ICSOC 2015), Goa, India, November 2015.

  • Approximation Algorithms Inspired by Kernelization Methods
    (joint work with C. Bazgan, M. Chopin and H. Fernau)
    in Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014),
    Lecture Notes in Computer Science, volume 8889, Jeonju, Korea, December 15-17, 2014, pages 479-490.

  • On the Parameterized Complexity of Dynamic Problems with Connectivity Constraints
    (joint work with J. Egan, M. R. Fellows, F. A. Rosamond and P. Shaw)
    in Proceedings of the 8th International Conference on Combinatorial Optimization and Applications (COCOA 2014),
    Lecture Notes in Computer Science, volume 8881, Wailea, Maui, HI, USA, December 19-21, 2014, pages 625-636.

  • On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism
    (joint work with E. Bonnet and F. Sikora)
    in Proceedings of the 25th International Workshop on Combinatorial Algorithms (IWOCA 2014),
    Lecture Notes in Computer Science, volume 8986, Duluth, MN, USA, October 15-17, 2014, pages 1-12.

  • The Multi-Parameterized Cluster Editing Problem
    in Proceedings of the 7th International Conference on Combinatorial Optimization and Applications (COCOA 2013),
    Lecture Notes in Computer Science, volume 8287, Chengdu, China, December 2013, pages 284-294.

  • A Decentralized Load Balancing Approach for Parallel Search-Tree Optimization
    (joint work with A. E. Mouawad)
    in Proceedings, the 13th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT-2012), December 2012.

  • An Improved Kernel for the Undirected Planar Feedback Vertex Set Problem
    (joint work with Mazen Bou Khuzam)
    in Proceedings, the 7th International Symposium on Parameterized and Exact Computation (IPEC-2012),
    Lecture Notes in Computer Science, volume 7535, Ljubliana, Slovenia, September 2012, pages 264-273.

  • Almost Exact Graph 3-Coloring in O(1.277^n) Time
    (joint work with M. A. Langston)
    in Proceedings, the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW-2012), May 2012.

  • A Degree-Based Heuristic for Strongly Connected Dominating-Absorbent Sets in Wireless Ad-Hoc Networks
    (joint work with C. Markarian)
    8th International Conference on Innovations in Information Technology, March 2012.

  • A Hybrid Graph Representation for Recursive Backtracking Algorithms
    (joint work with M. A. Langston, A. E. Mouawad and C. P. Nolan)
    in Proceedings of the 4th International Frontiers of Algorithmics Workshop (FAW 2010), Wuhan, China, August 2010, pages 136-147.

  • A Fixed-Parameter Algorithm for String-to-String Correction
    (joint work with H. Fernau, M. A. Langston, S. Lee-Cultura and U. Stege)
    in Proceedings of the 16th Computing: the Australasian Theory Symposium (CATS 2010),
    volume 109 of Conferences in Research and Practices in Information Technology CRPIT, pages 31-37. Australian Computer Society ACS, 2010.

  • A Quadratic Kernel for 3-Set Packing
    in Proceedings of the Sixth Annual Conference on Theory and Applications of Models of Computation, (TAMC 2009),
    Lecture Notes in Computer Science, volume 5532, Changsha, China, May 2009, pages 81-87.

  • Using Out-of-Core Techniques to Produce Exact Solutions to the Maximum Clique Problem on Extremely Large Graphs
    (joint work with Gary L. Rogers, Charles A. Phillips, John D. Eblen, Andy D. Perkins and Michael A. Langston)
    in Proceedings, ACS/IEEE International Conference on Computer Systems and Application (AICCSA 2009), Rabat, Morocco, May 2009.

  • Protein Structure Prediction in the 3D HP Model
    (joint work with F. Kanj, N. Mansour and H. Khachfe)
    in Proceedings, ACS/IEEE International Conference on Computer Systems and Application (AICCSA 2009), Rabat, Morocco, May 2009.

  • The Buffered Work-Pool Approach for Search-Tree Based Optimization Algorithms
    (joint work with M. A. Rizk)
    in Proceedings of the Seventh International Conference on Parallel Processing and Applied Mathematics, (PPAM-2007),
    Lecture Notes in Computer Science, volume 4967, Gdansk, Poland, September 2007, Pages 170-179.

  • Kernelization Algorithms for d-Hitting Set Problems
    in Proceedings of the 10th Workshop on Algorithms and Data Structures (WADS 2007),
    Lecture Notes in Computer Science, volume 4619, Halifax, Nova Scotia, Canada, August 2007, pages 434-445.

  • The Maximum Common Subgraph Problem: Faster Solutions via Vertex Cover
    (joint work with M. A. Rizk, N. F. Samatova and M. A. Langston)
    in Proceedings, ACS/IEEE International Conference on Computer Systems and Application (AICCSA 2007), Amman, Jordan, May 2007, pages 367-373.

  • Kernels: Annotated, Proper and Induced
    (jont work with Henning Fernau)
    in Proceedings of the 2nd International Workshop on Parameterized and Exact Computations (IWPEC 2006),
    Lecture Notes in Computer science, volume 4169, Zürich, Switzerland, September 13-15, 2006, pages 264-275.

  • Genome-Scale Computational Approaches to Memory-Intensive Applications in Systems Biology
    (joint work with N. E. Baldwin, E. J. Chesler, M. A. Langston, N. F. Samatova and Y. Zhang)
    in Proceedings of the ACM/IEEE SC-2005 Conference on High Performance Networking and Computing Seattle, Washington, November 12-18, 2005:12.

  • A New Approach and Faster Exact Methods for the Maximum Common Subgraph Problem
    (joint work with M. A. Langston, N. F. Samatova, W. H. Suters, C. T. Symons and Y. Zhang)
    in Proceedings of the 11th International Computing and Combinatorics Conference (COCOON 2005),
    Lecture Notes in Computer Science, volume 3595, Kunming, China, August, 2005, pages 717-727.

  • Linear-Time Algorithms for Problems on Planar Graphs of Fixed Disk Dimension
    (joint work with M. A. Langston)
    in Proceedings, the International Workshop on Algorithms and Complexity in Durham (ACiD 2005) Durham, England, July, 2005, pages 59-67.

  • Asymptotically Faster Algorithms for the Parameterized Face Cover Problem
    (joint work with M. A. Langston and H. Fernau)
    in Proceedings, International Workshop on Algorithms and Complexity in Durham (ACiD-2005), Durham, England, July, 2005, pages 43-58.

  • On the Relative Efficiency of Maximal Clique Enumeration Algorithms, with Application to High-Throughput Computational Biology
    (joint work with N. E. Baldwin, M. A. Langston and N. F. Samatova)
    in Proceedings, International Conference on Research Trends in Science and Technology, Beirut, Lebanon, March, 2005.

  • Fast, Effective Vertex Cover Kernelization: A Tale of Two Algorithms
    (joint work with M. A. Langston and W. H. Suters)
    in Proceedings, ACS/IEEE International Conference on Computer Systems and Applications, Cairo, Egypt, January, 2005:16.