Results 11 to 20 of about 1,396 (204)
On the First-Order Complexity of Induced Subgraph Isomorphism [PDF]
Logical Methods in Computer Science, 2019 Given a graph $F$, let $I(F)$ be the class of graphs containing $F$ as an induced subgraph. Let $W[F]$ denote the minimum $k$ such that $I(F)$ is definable in $k$-variable first-order logic.
Oleg Verbitsky, Maksim Zhukovskii
doaj +4 more sources
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 +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 ...
Zampelli, Stephane +5 more
+7 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
An experimental evaluation of refinement techniques for the subgraph isomorphism backtracking algorithms [PDF]
Open Computer Science, 2020 In this paper, we study a well-known computationally hard problem, called the subgraph isomorphism problem where the goal is for a given pattern and target graphs to determine whether the pattern is a subgraph of the target graph. Numerous algorithms for
Mihelič Jurij, Čibej Uroš
doaj +2 more sources
A Convex Relaxation Bound for Subgraph Isomorphism [PDF]
International Journal of Combinatorics, 2012 In this work a convex relaxation of a subgraph isomorphism problem is proposed, which leads to a new lower bound that can provide a proof that a subgraph isomorphism between two graphs can not be found. The bound is based on a semidefinite programming relaxation of a combinatorial optimisation formulation for subgraph isomorphism and is explained in ...
Christian Schellewald
openaire +3 more sources
Symmetry Breaking in Subgraph Isomorphism
, 2007 The present work studies symmetry breaking for the subgraph isomorphism problem. This NP-Complete problem decides if a pattern graph is isomorphic to a subgraph of a target graph. The first part of the paper shows how to detect and break all variable and value global symmetries.
Zampelli, Stéphane +4 more
openaire +3 more sources
A coding method for efficient subgraph querying on vertex- and edge-labeled graphs. [PDF]
PLoS ONE, 2014 Labeled graphs are widely used to model complex data in many domains, so subgraph querying has been attracting more and more attention from researchers around the world.
Lei Zhu +5 more
doaj +1 more source
TemporalRI: subgraph isomorphism in temporal networks with multiple contacts
Applied Network Science, 2021 Temporal networks are graphs where each edge is associated with a timestamp denoting when two nodes interact. Temporal Subgraph Isomorphism (TSI) aims at retrieving all the subgraphs of a temporal network (called target) matching a smaller temporal ...
Giovanni Micale +3 more
doaj +1 more source
Groups for which the noncommuting graph is a split graph [PDF]
International Journal of Group Theory, 2017 The noncommuting graph $nabla (G)$ of a group $G$ is a simple graph whose vertex set is the set of noncentral elements of $G$ and the edges of which are the ones connecting two noncommuting elements. We determine here, up to isomorphism, the structure of
Marzieh Akbari, Alireza Moghaddamfar
doaj +1 more source