Results 121 to 130 of about 23,139 (195)
The principles behind equivariant neural networks for physics and chemistry. [PDF]
Proc Natl Acad Sci U S AKondor R.
europepmc +1 more source
Heuristic sampling for the subgraph isomorphism problem [PDF]
2017 IEEE 14th International Scientific Conference on Informatics, 2017 Subgraph isomorphism is one of the fundamental search problems in computer science. In this article we consider the counting variation of this problem. The task is to count all instances of the pattern G occurring in a (usually larger) graph H. All algorithms for this problem use a variation of backtracking. Most commonly they assign one vertex of G to
Uroš Čibej, Jurij Mihelič
semanticscholar +3 more sources
A QUBO Formulation For the K-densest Common Subgraph Isomorphism Problem Via Quantum Annealing [PDF]
2020 IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE), 2020 In this paper, we extend the algorithm of [6] to solve the k-densest maximum common subgraph problem. By solving the k-densest maximum common subgraph isomorphism problem, we find high complexity common substructures between input graphs. We prove that our proposed objective function always gives the right answer to the corresponding QUBO problem.
Nan Huang
semanticscholar +3 more sources
A Backtracking Algorithmic Toolbox for Solving the Subgraph Isomorphism Problem
Advances in Systems Analysis, Software Engineering, and High Performance Computing, 2021 The subgraph isomorphism problem asks whether a given graph is a subgraph of another graph. It is one of the most general NP-complete problems since many other problems (e.g., Hamiltonian cycle, clique, independent set, etc.) have a natural reduction to subgraph isomorphism.
Jurij Mihelič +2 more
semanticscholar +3 more sources
A hybrid incremental genetic algorithm for subgraph isomorphism problem [PDF]
Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, 2014 Finding an isomorphic subgraph is a key problem in many real world applications modeled on graph. In this paper, we propose a new hybrid genetic algorithm(GA) for subgraph isomorphism problem which uses an incremental approach. We solve the problem with increasing the size of the subproblem step by step.
Hyukgeun Choi +2 more
semanticscholar +3 more sources
Developing Heuristic for Subgraph Isomorphism Problem
International Conference on Contemporary Computing, 2012 Subgraph isomorphism problem is an NP-hard problem and the available algorithms are of exponential time complexity. Hence these are not efficient for real world applications. A number of heuristic methods are proposed in the literature in this field. Ullmann[6] proposed a solution for subgraph isomorphism problem in 1976, which is being referred till ...
Saifuddin Kaijar, S. Durga Bhavani
semanticscholar +4 more sources
A genetic and iterative local search algorithm for solving subgraph isomorphism problem
2015 International Conference on Industrial Engineering and Operations Management (IEOM), 2015 Finding the subgraph of a graph that is isomorphic to a given graph has practicalapplications in several fields, from cheminformatics to image understanding. Since subgraph isomorphismproblem is NP-Hard, meta-heuristics are of especial use and importance in solving it. In this paper a hybrid metaheuristic algorithm for subgraph isomorphism is proposed.
Mina Mazraeh Farahani, S K Chaharsoughi
semanticscholar +4 more sources
Scoring-Based Neighborhood Dominance for the Subgraph Isomorphism Problem
International Conference on Principles and Practice of Constraint Programming, 2014 This paper presents an original filtering approach, called SND (Scoring-based Neighborhood Dominance), for the subgraph isomorphism problem. By reasoning on vertex dominance properties based on various scoring and neighborhood functions, SND appears to be a filtering mechanism of strong inference potential. For example, the recently proposed method LAD
Gilles Audemard +4 more
semanticscholar +5 more sources
Hardware accelerator for subgraph isomorphism problems [PDF]
Proceedings 2000 IEEE Symposium on Field-Programmable Custom Computing Machines (Cat. No.PR00871), 2002 Many applications can be modeled as subgraph isomorphism problems, which are generally NP-complete. This paper presents an algorithm that is suited for hardware implementation. The prototype accelerator that operates at 16.5 MHz on a Lucent ORCA 2C15A FPGA outperforms the software implementation of Ullmann's algorithm on a 400 MHz Pentium II by 10 ...
Shûichi Ichikawa +2 more
openalex +2 more sources