Relevant bibliographies by topics / Subgraph isomorphism

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Book chapters
  4. Conference papers

Academic literature on the topic 'Subgraph isomorphism'

Author: Grafiati
Published: 4 June 2021
Last updated: 25 July 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Subgraph isomorphism.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Subgraph isomorphism"

1

Duong, Chi Thang, Trung Dung Hoang, Hongzhi Yin, Matthias Weidlich, Quoc Viet Hung Nguyen, and Karl Aberer. "Efficient streaming subgraph isomorphism with graph neural networks." Proceedings of the VLDB Endowment 14, no. 5 (2021): 730–42. http://dx.doi.org/10.14778/3446095.3446097.

Full text
Abstract:
Queries to detect isomorphic subgraphs are important in graph-based data management. While the problem of subgraph isomorphism search has received considerable attention for the static setting of a single query, or a batch thereof, existing approaches do not scale to a dynamic setting of a continuous stream of queries. In this paper, we address the scalability challenges induced by a stream of subgraph isomorphism queries by caching and re-use of previous results. We first present a novel subgraph index based on graph embeddings that serves as the foundation for efficient stream processing. It
APA, Harvard, Vancouver, ISO, and other styles
2

Douar, Brahim, Chiraz Latiri, Michel Liquiere, and Yahya Slimani. "A Projection Bias in Frequent Subgraph Mining Can Make a Difference." International Journal on Artificial Intelligence Tools 23, no. 05 (2014): 1450005. http://dx.doi.org/10.1142/s0218213014500055.

Full text
Abstract:
The aim of the frequent subgraph mining task is to find frequently occurring subgraphs in a large graph database. However, this task is a thriving challenge, as graph and subgraph isomorphisms play a key role throughout the computations. Since subgraph isomorphism testing is a hard problem, subgraph miners are exponential in runtime. To alleviate the complexity issue, we propose to introduce a bias in the projection operator and instead of using the costly subgraph isomorphism projection, one can use a polynomial projection having a semantically-valid structural interpretation. This paper pres
APA, Harvard, Vancouver, ISO, and other styles
3

Koca, Mehmet Burak, and Fatih Erdoğan Sevilgen. "An Efficient Index-Based Algorithm for Exact Subgraph Isomorphism on Bipartite Graphs." Scientific Research Communications 4, no. 1 (2024): 44–60. https://doi.org/10.52460/src.2024.005.

Full text
Abstract:
Graphs are widely used to represent various real-world networks, but their non-linear nature and size increase pose challenges for efficient analysis. The subgraph isomorphism problem, which involves identifying subgraphs that are isomorphic to a query graph, plays a crucial role in diverse domains. In this paper, we focus on the exact subgraph isomorphism problem in bipartite graphs and propose a novel index-based solution algorithm. Our algorithm leverages triplet structures for graph embedding and uses a multi-level hash map for efficient filtering. We also introduce an optimized solution b
APA, Harvard, Vancouver, ISO, and other styles
4

Demetrovics, J., H. M. Quang, N. V. Anh, and V. D. Thi. "An Optimization of Closed Frequent Subgraph Mining Algorithm." Cybernetics and Information Technologies 17, no. 1 (2017): 3–15. http://dx.doi.org/10.1515/cait-2017-0001.

Full text
Abstract:
Abstract Graph mining isamajor area of interest within the field of data mining in recent years. Akey aspect of graph mining is frequent subgraph mining. Central to the entire discipline of frequent subgraph mining is the concept of subgraph isomorphism. One major issue in early subgraph isomorphism research concerns computational complexity. Normally, the subgraph isomorphism problem is NP-complete. Previous studies of frequent subgraph mining have not solved NP-complete problem in the subgraph isomorphism. In this paper, we proposeanew algorithm which can deal with this problem. The proposed
APA, Harvard, Vancouver, ISO, and other styles
5

Xu, Zifeng, Fucai Zhou, Yuxi Li, Jian Xu, and Qiang Wang. "Privacy-Preserving Subgraph Matching Protocol for Two Parties." International Journal of Foundations of Computer Science 30, no. 04 (2019): 571–88. http://dx.doi.org/10.1142/s0129054119400136.

Full text
Abstract:
Graph data structure has been widely used across many application areas, such as web data, social network, and cheminformatics. The main benefit of storing data as graphs is there exists a rich set of graph algorithms and operations that can be used to solve various computing problems, including pattern matching, data mining, and image processing. Among these graph algorithms, the subgraph isomorphism problem is one of the most fundamental algorithms that can be utilized by many higher level applications. The subgraph isomorphism problem is defined as, given two graphs [Formula: see text] and
APA, Harvard, Vancouver, ISO, and other styles
6

Schellewald, Christian. "A Convex Relaxation Bound for Subgraph Isomorphism." International Journal of Combinatorics 2012 (February 7, 2012): 1–18. http://dx.doi.org/10.1155/2012/908356.

Full text
Abstract:
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 detail. We consider subgraph isomorphism problem instances of simple graphs which means that only the structural information of the two graphs is exploited and other information that might be available (e.g., node positions) is ignored. The bound i
APA, Harvard, Vancouver, ISO, and other styles
7

Liu, Xin, and Yangqiu Song. "Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 7 (2022): 7594–602. http://dx.doi.org/10.1609/aaai.v36i7.20725.

Full text
Abstract:
Graph neural networks (GNNs) and message passing neural networks (MPNNs) have been proven to be expressive for subgraph structures in many applications. Some applications in heterogeneous graphs require explicit edge modeling, such as subgraph isomorphism counting and matching. However, existing message passing mechanisms are not designed well in theory. In this paper, we start from a particular edge-to-vertex transform and exploit the isomorphism property in the edge-to-vertex dual graphs. We prove that searching isomorphisms on the original graph is equivalent to searching on its dual graph.
APA, Harvard, Vancouver, ISO, and other styles
8

Chu, Yang Jie, and Xin Jia. "An Improved Algorithm on Frequent Subgraph Query." Applied Mechanics and Materials 623 (August 2014): 169–73. http://dx.doi.org/10.4028/www.scientific.net/amm.623.169.

Full text
Abstract:
This paper studies the frequent subgraph query issues on graph data set. Combining with the approach that frequent subtree extend to frequent subgraphs proposed by Xian-Tong Li, we propose a new algorithm. This algorithm improved its storage structure avoiding direct subgraph isomorphism judgment, reduced the stability requirements on graph set, and enchanced the overall efficiency of the algorithm.
APA, Harvard, Vancouver, ISO, and other styles
9

Li, Feng. "An efficient mining algorithm for maximal frequent patterns in uncertain graph database." Journal of Intelligent & Fuzzy Systems 39, no. 5 (2020): 7021–33. http://dx.doi.org/10.3233/jifs-200237.

Full text
Abstract:
Mining maximal frequent patterns is significant in many fields, but the mining efficiency is often low. The bottleneck lies in too many candidate subgraphs and extensive subgraph isomorphism tests. In this paper we propose an efficient mining algorithm. There are two key ideas behind the proposed methods. The first is to divide each edge of every certain graph (converted from equivalent uncertain graph) and build search tree, avoiding too many candidate subgraphs. The second is to search the tree built in the first step in order, avoiding extensive subgraph isomorphism tests. The evaluation of
APA, Harvard, Vancouver, ISO, and other styles
10

Jiang, Lincheng, Xiang Zhao, Bin Ge, et al. "On Minimal Unique Induced Subgraph Queries." Applied Sciences 8, no. 10 (2018): 1798. http://dx.doi.org/10.3390/app8101798.

Full text
Abstract:
In this paper, a novel type of interesting subgraph query is proposed: Minimal Unique Induced Subgraph (MUIS) query. Given a (large) graph G and a query vertex (position) q in the graph, can we find an induced subgraph containing q with the minimal number of vertices that is unique in G? MUIS query has many potential applications, such as subgraph retrieval, graph visualization, representative subgraph discovery and vertex property exploration. The formal definition of MUIS is given and the properties are discussed in this paper. The baseline and EQA (Efficient Query Answering) algorithms are
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Subgraph isomorphism"

1

Nabti, Chems Eddine. "Subgraph Isomorphism Search In Massive Graph Data." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSE1293/document.

Full text
Abstract:
L'interrogation de graphes de données est un problème fondamental qui connait un grand intérêt, en particulier pour les données structurées massives où les graphes constituent une alternative prometteuse aux bases de données relationnelles pour la modélisation des grandes masses de données. Cependant, l'interrogation des graphes de données est différente et plus complexe que l'interrogation des données relationnelles à base de tables. La tâche principale impliquée dans l'interrogation de graphes de données est la recherche d'isomorphisme de sous-graphes qui est un problème NP-complet.La recher
APA, Harvard, Vancouver, ISO, and other styles
2

Ren, Xuguang. "Speeding up Subgraph Isomorphism Search in Large Graphs." Thesis, Griffith University, 2018. http://hdl.handle.net/10072/381513.

Full text
Abstract:
Graph is a widely used model to represent complicated data in many domains. Finding subgraph isomorphism is a fundamental function for many graph databases and data mining applications handling graph data. This thesis studies this classic problem by considering a set of novel techniques from three different aspects. This thesis first considers speeding up subgraph isomorphism search by exploiting relationships among data vertices. Most of the subgraph isomorphism algorithms of the In-Memory model (IM) are based on a backtracking method which computes the solutions by incrementally enumerating
APA, Harvard, Vancouver, ISO, and other styles
3

Minot, Maël. "Investigating decomposition methods for the maximum common subgraph and sum colouring problems." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSEI120/document.

Full text
Abstract:
Notre objectif est d’évaluer et de rendre opérationnelle la décomposition de problèmes d’optimisation sous contraintes. Nous nous sommes intéressés à deux problèmes en particulier : le problème de la recherche d’un plus grand sous-graphe commun (MCIS), et le problème de somme coloration minimale (MSCP). Il s’agit de problèmes NP-difficiles pour lesquels les approches de résolution complètes passent difficilement à l’échelle, et nous proposons de les améliorer à cet égard en décomposant ces problèmes en sous-problèmes indépendants. Les décompositions que nous proposons s’appuient sur la structu
APA, Harvard, Vancouver, ISO, and other styles
4

Hourcade, Hugo. "Énumération de motifs temporels." Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS079.

Full text
Abstract:
Dans le cadre de l'étude des interactions de divers acteurs au sein d'un système, la recherche de schémas comportementaux trouve nombre d'applications. Les graphes temporels qui m'intéressent dans le cadre de cette thèse présentent des tailles d'historiques tau, à savoir le nombre d'instants temporels entre le premier instant t0 et le dernier instant tf pour lesquels G n'est pas vide, de l'ordre de plusieurs millions. Je cherche donc à minimiser l'impact de tau sur les complexités spatiales et temporelles de mes algorithmes. Étant donné Delta un entier naturel, l'énumération de Delta-modules e
APA, Harvard, Vancouver, ISO, and other styles
5

Tian, Chao. "Towards effective analysis of big graphs : from scalability to quality." Thesis, University of Edinburgh, 2017. http://hdl.handle.net/1842/29578.

Full text
Abstract:
This thesis investigates the central issues underlying graph analysis, namely, scalability and quality. We first study the incremental problems for graph queries, which aim to compute the changes to the old query answer, in response to the updates to the input graph. The incremental problem is called bounded if its cost is decided by the sizes of the query and the changes only. No matter how desirable, however, our first results are negative: for common graph queries such as graph traversal, connectivity, keyword search and pattern matching, their incremental problems are unbounded. In light o
APA, Harvard, Vancouver, ISO, and other styles
6

Hofton, Antony Edward. "Graph layout using subgraph isomorphisms." Thesis, Durham University, 2000. http://etheses.dur.ac.uk/4337/.

Full text
Abstract:
Today, graphs are used for many things. In engineering, graphs are used to design circuits in very large scale integration. In computer science, graphs are used in the representation of the structure of software. They show information such as the flow of data through the program (known as the data flow graph [1]) or the information about the calling sequence of programs (known as the call graph [145]). These graphs consist of many classes of graphs and may occupy a large area and involve a large number of vertices and edges. The manual layout of graphs is a tedious and error prone task. Algori
APA, Harvard, Vancouver, ISO, and other styles
7

Stejskal, Roman. "Zjišťování izomorfizmu grafů v databázi." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2008. http://www.nusl.cz/ntk/nusl-236007.

Full text
Abstract:
This project introduces history and basic notions of the graph theory. It describes graph theory problems, possible graph representations and practical graph management in databases. Aims to subgraph and graph isomorphism. It describes possible ways to find graph isomorphism and chosen algorithms for subgraph and graph isomorphism. The experimental part aims to comparing two implemented algorithms. These are Ullmann and VF2 algorithm. Also searches difference between graphs stored in memory and graphs stored in database.
APA, Harvard, Vancouver, ISO, and other styles
8

Vergara, John Paul C. "Edge-packing by isomorphic subgraphs." Thesis, Virginia Tech, 1990. http://hdl.handle.net/10919/42147.

Full text
Abstract:
Maximum G Edge-Packing (E Pack<sub>G</sub>) is the problem of finding the maximum number of edge-disjoint isomorphic copies of a fixed guest graph G in a host graph H. The problem is primarily considered for several guest graphs (stars, paths and cycles) and host graphs (arbitrary graphs, planar graphs and trees). We give polynomial-time algorithms when G is a 2-path or when H is a tree; we show the problem is NP-complete otherwise. Also, we propose straightforward greedy polynomial-time approximation algorithms which are at least 1/|E<sub>G</sub>| optimal.<br>Master of Science
APA, Harvard, Vancouver, ISO, and other styles
9

Ševčík, Ivan. "Systém pro vyhledávání chemických struktur." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2018. http://www.nusl.cz/ntk/nusl-385936.

Full text
Abstract:
This thesis deals with the problem of searching of structures in large chemical compounds databases. The aim is to design and implement an efficient system that supports two basic types of search, which are identity and substructure search. This task is complicated not only by the large number of entries in databases but also by graph representation of chemical structures, for which many algorithms are hard to solve. The thesis will introduce concepts which will prove useful in solving these problems. A web service is also created as a part of the thesis in order to make the database searching
APA, Harvard, Vancouver, ISO, and other styles
10

Oberoi, Kamaldeep Singh. "Modélisation spatio-temporelle du trafic routier en milieu urbain." Thesis, Normandie, 2019. http://www.theses.fr/2019NORMR075/document.

Full text
Abstract:
Le domaine de la modélisation du trafic routier vise à comprendre son évolution. Dans les dernières années, plusieurs modèles du trafic ont été proposés dans l’objectif de géolocaliser les embouteillages au sein du trafic, détecter des motifs dans le trafic routier, estimer l’état du trafic etc. La plupart des modèles proposés considèrent le trafic routier en termes de ses constituants ou comme une entité agrégée en fonction de l’échelle choisie et expliquent l’évolution du trafic quantitativement en tenant compte des relations entre les variables de trafic comme le flot, la densité et la vite
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Subgraph isomorphism"

1

Kotthoff, Lars, Ciaran McCreesh, and Christine Solnon. "Portfolios of Subgraph Isomorphism Algorithms." In Lecture Notes in Computer Science. Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-50349-3_8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Solnon, Christine. "Experimental Evaluation of Subgraph Isomorphism Solvers." In Graph-Based Representations in Pattern Recognition. Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-20081-7_1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Carletti, Vincenzo, Pasquale Foggia, Pierluigi Ritrovato, Mario Vento, and Vincenzo Vigilante. "A Parallel Algorithm for Subgraph Isomorphism." In Graph-Based Representations in Pattern Recognition. Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-20081-7_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Kaijar, Saifuddin, and S. Durga Bhavani. "Developing Heuristic for Subgraph Isomorphism Problem." In Communications in Computer and Information Science. Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-32129-0_10.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Jiang, Xiaoyi, and Horst Bunke. "Marked subgraph isomorphism of ordered graphs." In Advances in Pattern Recognition. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0033230.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Čibej, Uroš, and Jurij Mihelič. "Search Strategies for Subgraph Isomorphism Algorithms." In Applied Algorithms. Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-04126-1_7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Fuchs, Frank, and Hervé Le-Men. "Efficient Subgraph Isomorphism with ‘A Priori’ Knowledge." In Advances in Pattern Recognition. Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-44522-6_44.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Ichikawa, Shuichi, and Shoji Yamamoto. "Data Dependent Circuit for Subgraph Isomorphism Problem." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/3-540-46117-5_109.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Anton, Cǎlin, and Lane Olson. "Generating Satisfiable SAT Instances Using Random Subgraph Isomorphism." In Advances in Artificial Intelligence. Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-01818-3_5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Weber, Markus, Christoph Langenhan, Thomas Roth-Berghofer, Marcus Liwicki, Andreas Dengel, and Frank Petzold. "Fast Subgraph Isomorphism Detection for Graph-Based Retrieval." In Case-Based Reasoning Research and Development. Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-23291-6_24.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Subgraph isomorphism"

1

Bosio, Roberto, Giovanni Brignone, Filippo Minnella, M. Usman Jamal, and Luciano Lavagno. "LESS: Low-Power Energy-Efficient Subgraph Isomorphism on FPGA." In 2024 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 2024. http://dx.doi.org/10.23919/date58400.2024.10546632.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Tauhidi, Syed Ibtisam, Arindam Karmakar, Thai Son Mai, and Hans Vandierendonck. "OrbitSI: An Orbit-based Algorithm for the Subgraph Isomorphism Search Problem." In 2024 IEEE International Conference on Knowledge Graph (ICKG). IEEE, 2024. https://doi.org/10.1109/ickg63256.2024.00052.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Xiao, Yifeng, Chanwook Oh, Michele Lora, and Pierluigi Nuzzo. "Efficient Exploration of Cyber-Physical System Architectures Using Contracts and Subgraph Isomorphism." In 2024 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 2024. http://dx.doi.org/10.23919/date58400.2024.10546764.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Redmond, Ursula, and Pádraig Cunningham. "Temporal subgraph isomorphism." In ASONAM '13: Advances in Social Networks Analysis and Mining 2013. ACM, 2013. http://dx.doi.org/10.1145/2492517.2492586.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Liu, Xin, Haojie Pan, Mutian He, Yangqiu Song, Xin Jiang, and Lifeng Shang. "Neural Subgraph Isomorphism Counting." In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM, 2020. http://dx.doi.org/10.1145/3394486.3403247.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Samsi, Siddharth, Vijay Gadepally, Michael Hurley, et al. "Static graph challenge: Subgraph isomorphism." In 2017 IEEE High-Performance Extreme Computing Conference (HPEC). IEEE, 2017. http://dx.doi.org/10.1109/hpec.2017.8091039.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Zeng, Li, Lei Zou, M. Tamer Ozsu, Lin Hu, and Fan Zhang. "GSI: GPU-friendly Subgraph Isomorphism." In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 2020. http://dx.doi.org/10.1109/icde48307.2020.00112.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

ROSSMAN, BENJAMIN. "LOWER BOUNDS FOR SUBGRAPH ISOMORPHISM." In International Congress of Mathematicians 2018. WORLD SCIENTIFIC, 2019. http://dx.doi.org/10.1142/9789813272880_0187.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Amano, Kazuyuki. "k-Subgraph Isomorphism on AC_0 Circuits." In 2009 24th Annual IEEE Conference on Computational Complexity (CCC). IEEE, 2009. http://dx.doi.org/10.1109/ccc.2009.23.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Gocht, Stephan, Ciaran McCreesh, and Jakob Nordström. "Subgraph Isomorphism Meets Cutting Planes: Solving With Certified Solutions." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/158.

Full text
Abstract:
Modern subgraph isomorphism solvers carry out sophisticated reasoning using graph invariants such as degree sequences and path counts. We show that all of this reasoning can be justified compactly using the cutting planes proofs studied in complexity theory. This allows us to extend a state of the art subgraph isomorphism enumeration solver with proof logging support, so that the solutions it outputs may be audited and verified for correctness and completeness by a simple third party tool which knows nothing about graph theory.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Subgraph isomorphism' for particular source types:
Journal articles Dissertations / Theses
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography