Results 71 to 80 of about 101,745 (269)
The Hardness of Subgraph Isomorphism
, 2015 Subgraph Isomorphism is a very basic graph problem, where given two graphs $G$ and $H$ one is to check whether $G$ is a subgraph of $H$. Despite its simple definition, the Subgraph Isomorphism problem turns out to be very broad, as it generalizes problems such as Clique, $r$-Coloring, Hamiltonicity, Set Packing and Bandwidth.
Cygan, Marek +2 more
openaire +2 more sources
On the Variable Ordering in Subgraph Isomorphism Algorithms
IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2017 Graphs are mathematical structures to model several biological data. Applications to analyze them require to apply solutions for the subgraph isomorphism problem, which is NP-complete. Here, we investigate the existing strategies to reduce the subgraph isomorphism algorithm running time with emphasis on the importance of the order with which the graph ...
Bonnici Vincenzo, Giugno Rosalba
openaire +5 more sources
Affine equivalence and saddle connection graphs of half-translation surfaces
, 2020 To every half-translation surface, we associate a saddle connection graph, which is a subgraph of the arc graph. We prove that every isomorphism between two saddle connection graphs is induced by an affine homeomorphism between the underlying half ...
Pan, Huiping
core +1 more source
Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases [PDF]
, 2012 Many studies have been conducted on seeking the efficient solution for subgraph similarity search over certain (deterministic) graphs due to its wide application in many fields, including bioinformatics, social network analysis, and Resource Description ...
Chen, Lei +3 more
core +3 more sources
SICode: Embedding-Based Subgraph Isomorphism Identification for Bug Detection
IEEE International Conference on Program ComprehensionGiven a known buggy code snippet, searching for similar patterns in a target project to detect unknown bugs is a reasonable approach. In practice, a search unit, such as a function, may appear quite different from the buggy snippet but actually contains ...
Yuanjun Gong +6 more
semanticscholar +1 more source
Graphs with Isomorphic Neighbor-subgraphs
Taiwanese Journal of Mathematics, 2011 A graph $G$ is said to be $H$-regular if for each vertex $v\in V(G)$, the graph induced by $N_G(v)$ is isomorphic to $H$. A graph $H$ is a feasible neighbor-subgraph if there exists an H-regular graph, otherwise H is a forbidden neighbor-subgraph. In this paper, we obtain some classes of graphs $H$ which are forbidden and then we focus on searching $H$-
Chan, Chi-Feng +2 more
openaire +3 more sources
Efficient Algorithms for Subgraph Listing
Algorithms, 2014 Subgraph isomorphism is a fundamental problem in graph theory. In this paper we focus on listing subgraphs isomorphic to a given pattern graph. First, we look at the algorithm due to Chiba and Nishizeki for listing complete subgraphs of fixed size, and ...
Niklas Zechner, Andrzej Lingas
doaj +1 more source
Defining Recursive Predicates in Graph Orders [PDF]
Logical Methods in Computer Science, 2018 We study the first order theory of structures over graphs i.e. structures of the form ($\mathcal{G},\tau$) where $\mathcal{G}$ is the set of all (isomorphism types of) finite undirected graphs and $\tau$ some vocabulary.
Ramanathan S. Thinniyam
doaj +1 more source
A Partitioning Algorithm for Maximum Common Subgraph Problems [PDF]
, 2017 We introduce a new branch and bound algorithm for the maximum common subgraph and maximum common connected subgraph problems which is based around vertex labelling and partitioning.
McCreesh, Ciaran +2 more
core +2 more sources
Weighted Turán Theorems With Applications to Ramsey‐Turán Type of Problems
Journal of Graph Theory, EarlyView.ABSTRACT We study extensions of Turán Theorem in edge‐weighted settings. A particular case of interest is when constraints on the weight of an edge come from the order of the largest clique containing it. These problems are motivated by Ramsey‐Turán type problems.
József Balogh +2 more
wiley +1 more source