Results 1 to 10 of about 17,360 (200)
SEARCH-TREE SIZE ESTIMATION FOR THE SUBGRAPH ISOMORPHISM PROBLEM [PDF]
Acta Electrotechnica et Informatica, 2019 This article addresses the problem of finding patterns in graphs. This is formally defined as the subgraph isomorphism problem and is one of the core problems in theoretical computer science. We consider the counting variation of this problem.
Uroš Čibej, Jurij MIHELIČ
doaj +3 more sources
The Glasgow Subgraph Solver: Using Constraint Programming to Tackle Hard Subgraph Isomorphism Problem Variants [PDF]
Graph Transformation13th International Conference, 2020 The Glasgow Subgraph Solver provides an implementation of state of the art algorithms for subgraph isomorphism problems. It combines constraint programming concepts with a variety of strong but fast domain-specific search and inference techniques, and is suitable for use on a wide range of graphs, including many that are found to be computationally ...
McCreesh C, Prosser P, Trimble J.
europepmc +6 more sources
Recursive-Parallel Algorithm for Solving the Graph-Subgraph Isomorphism Problem
Моделирование и анализ информационных систем, 2022 The paper proposes a parallel algorithm for solving the Graph-Subgraph Isomorphism Problem and makes an experimental study of its efficiency. The problem is one of the most famous NP-complete problems.
Vladimir V. Vasilchikov
doaj +4 more sources
Subgraph Isomorphism in Planar Graphs and Related Problems [PDF]
Journal of Graph Algorithms and Applications, 1999 27 pages, 6 figures. A preliminary version of this paper appeared at the 6th ACM-SIAM Symp.
David Eppstein
+8 more sources
Solving subgraph isomorphism problems with constraint programming [PDF]
Constraints, 2009 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Zampelli, Stéphane +2 more
openaire +6 more sources
PathLAD+: An Improved Exact Algorithm for Subgraph Isomorphism Problem [PDF]
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023 The subgraph isomorphism problem (SIP) is a challenging problem with wide practical applications. In the last decade, despite being a theoretical hard problem, researchers design various algorithms for solving SIP. In this work, we propose three main heuristics and develop an improved exact algorithm for SIP. First, we design a probing search procedure
Yiyuan Wang +3 more
openaire +2 more sources
An Improved Heuristic Method for Subgraph Isomorphism Problem [PDF]
IOP Conference Series: Materials Science and Engineering, 2017 This paper focus on the subgraph isomorphism (SI) problem. We present an improved genetic algorithm, a heuristic method to search the optimal solution. The contribution of this paper is that we design a dedicated crossover algorithm and a new fitness function to measure the evolution process.
Yingzhuo Xiang +3 more
openaire +2 more sources
Solving Graph Homomorphism and Subgraph Isomorphism Problems Faster Through Clique Neighbourhood Constraints [PDF]
Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, 2021 Graph homomorphism problems involve finding adjacency-preserving mappings between two given graphs. Although theoretically hard, these problems can often be solved in practice using constraint programming algorithms. We show how techniques from the state-of-the-art in subgraph isomorphism solving can be applied to broader graph homomorphism problems ...
Kraiczy, Sonja, McCreesh, Ciaran
openaire +3 more sources
Efficient Implementation of Color Coding Algorithm for Subgraph Isomorphism Problem [PDF]
, 2019 We consider the subgraph isomorphism problem where, given two graphs G (source graph) and F (pattern graph), one is to decide whether there is a (not necessarily induced) subgraph of G isomorphic to F. While many practical heuristic algorithms have been developed for the problem, as pointed out by McCreesh et al. [JAIR 2018], for each of them there are
Josef Malík +2 more
+6 more sources
GRAPH-SUBGRAPH ISOMORPHISM PROBLEM SOLVING FOR DESIGNING SPECIAL COMPUTERS
Radio Electronics, Computer Science, Control, 2012 An advanced algorithm for solving graphs isomorphism problem is proposed and experimental results of its efficiency are presented. Object of investigation is set of control flow graphs of solutions achieved, that were received after circumvent of the semantic network by Warren abstract machine.
M.B. Il’yashenko, A.A. Goldobin
openaire +3 more sources