Results 11 to 20 of about 102,063 (249)
Between Subgraph Isomorphism and Maximum Common Subgraph [PDF]
Proceedings of the AAAI Conference on Artificial Intelligence, 2017 When a small pattern graph does not occur inside a larger target graph, we can ask how to find "as much of the pattern as possible" inside the target graph. In general, this is known as the maximum common subgraph problem, which is much more computationally challenging in practice than subgraph isomorphism.
Hoffmann, Ruth +2 more
openaire +4 more sources
Neural Subgraph Isomorphism Counting [PDF]
Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2019 In this paper, we study a new graph learning problem: learning to count subgraph isomorphisms. Different from other traditional graph learning problems such as node classification and link prediction, subgraph isomorphism counting is NP-complete and ...
Xin Liu +4 more
semanticscholar +5 more sources
Optimized Backtracking for Subgraph Isomorphism [PDF]
International Journal of Database Management Systems, 2012 Subgraph isomorphism is a fundamental graph problem with many important applications. Given two graphs G and SG, the subgraph isomorphism problem is to determine whether G contains a subgraph that is isomorphic to SG. It is well known that the problem is NP complete in the worst case.
Lixin Fu
openalex +2 more sources
Planar Subgraph Isomorphism Revisited [PDF]
, 2009 13 pages, 4 ...
Frederic Dorn
openalex +7 more sources
Solving Graph Homomorphism and Subgraph Isomorphism Problems Faster Through Clique Neighbourhood Constraints [PDF]
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-
Sonja Kraiczy, Ciaran McCreesh
semanticscholar +2 more sources
Filtering for Subgraph Isomorphism [PDF]
, 2007 A subgraph isomorphism problem consists in deciding if there exists a copy of a pattern graph in a target graph. We introduce in this paper a filtering algorithm dedicated to this problem. The main idea is to label every node with respect to its relationships with other nodes of the graph, and to define a partial order on these labels in order to ...
Stéphane Zampelli +4 more
openalex +5 more sources
Practical Bigraphs via Subgraph Isomorphism [PDF]
International Conference on Principles and Practice of Constraint Programming, 2021 Bigraphs simultaneously model the spatial and non-spatial relationships between entities, and have been used for systems modelling in areas including biology, networking, and sensors. Temporal evolution can be modelled through a rewriting system, driven by a matching algorithm that identifies instances of bigraphs to be rewritten. The previous state-of-
B. Archibald +3 more
semanticscholar +5 more sources
Low-Power Subgraph Isomorphism at the Edge Using FPGAs
IEEE AccessSubgraph matching is a significant problem in several fields, including like social network analysis, chemical compound search, and fraud detection. While current solutions using CPU, graphics processing units (GPUs), and data center field-programmable ...
Roberto Bosio +5 more
doaj +2 more sources
GSI: GPU-friendly Subgraph Isomorphism [PDF]
2020 IEEE 36th International Conference on Data Engineering (ICDE), 2019 Subgraph isomorphism is a well-known NP-hard problem that is widely used in many applications, such as social network analysis and querying over the knowledge graph.
Li Zeng +4 more
semanticscholar +4 more sources
Parallel Planar Subgraph Isomorphism and Vertex Connectivity [PDF]
ACM Symposium on Parallelism in Algorithms and Architectures, 2020 We present the first parallel fixed-parameter algorithm for subgraph isomorphism in planar graphs, bounded-genus graphs, and, more generally, all minor-closed graphs of locally bounded treewidth.
Lukas Gianinazzi, T. Hoefler
semanticscholar +3 more sources