.

Browsing School of Arts and Sciences by Author "Langston, Micheal A."

LAUR Repository

Browsing School of Arts and Sciences by Author "Langston, Micheal A."

Sort by: Order: Results:

  • Asymptotically faster algorithms for parameterized FACE COVER 
    Abu-Khzam, Faisal N.; Fernau, Henning; Langston, Micheal A. (2018-04-26)
    The parameterized complexity of the face cover prob- lem is considered. The input to this problem is a plane graph, G, of order n. The question asked is whether, for any fixed k, there exists a set of k or fewer vertices ...
  • A bounded search tree algorithm for parameterized 
    Abu-Khzam, Faisal N.; Fernau, Henning; Langston, Micheal A. (2015-12-07)
    The parameterized complexity of the face cover problem is considered. The input to this problem is a plane graph G with n vertices. The question asked is whether, for a given parameter value k, there exists a set of k or ...
  • Charge and reduce 
    Abu-Khzam, Faisal N.; Fernau, Henning; Langston, Micheal A.; Lee-Cultura, Serena; Stege, Ulrike (2015-12-07)
    String distance problems typically ask for a minimum number of permitted operations to transform one string into another. Such problems find application in a wide variety of areas, including error-correcting codes, parsing ...
  • Crown Structures for Vertex Cover Kernelization 
    Abu-Khzam, Faisal N.; Fellos, Micheal R.; Langston, Micheal A.; Suters, W. Henry (2015-12-07)
    Crown structures in a graph are defined and shown to be useful in kernelization algorithms for the classic vertex cover problem. Two vertex cover kernelization methods are discussed. One, based on linear programming, has ...
  • A direct algorithm for the parameterized face cover problem 
    Abu-Khzam, Faisal N.; Langston, Micheal A. (Springer, 2017-03-21)
    With respect to a given plane graph, G, a face cover is defined as a set of faces whose boundaries collectively contain every vertex in G. It is known that, when k is fixed, finding a cover of size k (if indeed any exist) ...
  • Faces in the crowd 
    Abu-Khzam, Faisal N.; Langston, Micheal A. (2017-03-22)
    We study a pair of N P-hard problems aimed at finding small sets of faces in planar graphs. In the disk dimension problem, we are given a planar graph G, and seek the least number k for which G embeds in the plane minus k ...
  • Graph coloring and the immersion order 
    Abu-Khzam, Faisal N.; Langston, Micheal A. (Springer, 2017-03-21)
    The relationship between graph coloring and the immersion order is considered. Vertex connectivity, edge connectivity and related issues are explored. These lead to the conjecture that, if G requires at least t colors, ...
  • Grid computing 
    Abu-Khzam, Faisal N.; Langston, Micheal A. (ACM, 2018-04-24)
  • A high-performance toolkit for fast exact algorithms 
    Abu-Khzam, Faisal N.; Langston, Micheal A.; Shanbhag, Pushkar (2017-03-22)
    Ongoing work is described in which fast graph algorithms are combined with parallel, grid and reconfigurable technologies. This synergistic strategy can help solve problem instances too large or too difficult for standard ...
  • 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 ...
  • 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 ...
  • 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. ...
  • 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 ...
  • 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 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 ...
  • 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 ...
  • 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