2026-05-22T04:29:08Zhttps://keep.lib.asu.edu/oai/request

oai:keep.lib.asu.edu:node-1992832024-12-23T18:01:48Zoai_pmh:alloai_pmh:repo_items

199283 https://hdl.handle.net/2286/R.2.N.199283 http://rightsstatements.org/vocab/InC/1.0/ All Rights Reserved 2024 56 pages Masters Thesis Academic theses Text eng Patel, Devansh Bazzi, Rida A Daymude, Joshua J Richa, Andréa W Arizona State University Partial requirement for: M.S., Arizona State University, 2024 Field of study: Computer Science The decision problem of determining the existence of an isomorphism between apattern graph P and any subgraph of a target graph T is the Subgraph Isomorphism problem. The problem is classically known to be NP-complete, and generalizes many other structural NP-complete problems, such as the problem of finding a clique of certain size in a graph, or the problem of finding a Hamiltonian path in a graph. Subgraph isomorphism solvers have numerous practical applications in biochemistry, pattern recognition, and computer vision. The main contributions of this thesis follow: - I describe practical methods to solve instances of the subgraph isomorphism problem. Building on the techniques of Cordella et al., I introduce novel heuristics to prune the search space explored by a backtracking search algorithm. The primary heuristics I describe are methods of refining the compatibility of pairs of vertices during the backtracking search. These methods filter incompatible pairs by comparing partitions of the set of degrees of vertices in the pattern and target graphs. - I describe a method to approximate the optimal solution to the the minimum-weight subgraph isomorphism problem. This problem is a challenging weighted variant of the subgraph isomorphism problem, for which naive algorithms are expensive and exhaustive. The method is based on the backtracking framework and uses the rollout technique of Bertsekas. Computer Science Applied Mathematics Heuristic Search Rollout Method Subgraph Isomorphism Subgraph Isomorphism: Heuristics, Approximations, and Hardness Results