Results 1 to 10 of about 564 (166)
Efficient Algorithms for Subgraph Listing [PDF]
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 ...
Andrzej Lingas, Lingas Andrzej
exaly +7 more sources
DDSL: Efficient Subgraph Listing on Distributed and Dynamic Graphs [PDF]
Lecture Notes in Computer Science, 2020 Subgraph listing is a fundamental problem in graph theory and has wide applications in areas like sociology, chemistry, and social networks. Modern graphs can usually be large-scale as well as highly dynamic, which challenges the efficiency of existing subgraph listing algorithms.
Xun Jian, Yanyan Shen, Shen Yanyan
exaly +5 more sources
A Fine-Grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
Proceedings of the 57th Annual ACM Symposium on Theory of ComputingIn an $m$-edge host graph $G$, all triangles can be listed in time $O(m^{1.5})$ [Itai, Rodeh '78], and all $k$-cycles can be listed in time $O(m^{2-1/{\lceil k/2 \rceil}} + t)$ where $t$ is the output size [Alon, Yuster, Zwick '97]. These classic results also hold for the colored problem variant, where the nodes of the host graph $G$ are colored by ...
Karl Bringmann, Egor Gorbachev
exaly +8 more sources
Space-Query Tradeoffs in Range Subgraph Counting and Listing [PDF]
CoRR, 2023 This paper initializes the study of {\em range subgraph counting} and {\em range subgraph listing}, both of which are motivated by the significant demands in practice to perform graph analytics on subgraphs pertinent to only selected, as opposed to all, vertices.
Deng, Shiyuan, Lu, Shangqi, Tao, Yufei
openaire +5 more sources
Arboricity and bipartite subgraph listing algorithms [PDF]
Information Processing Letters, 1994 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
David Eppstein
exaly +3 more sources
DIST: Efficient k-Clique Listing via Induced Subgraph Trie
VLDB JournalListing k-cliques plays a fundamental role in various data mining tasks, such as community detection and mining of cohesive substructures. Existing algorithms for the k-clique listing problem are built upon a general framework, which finds k-cliques by recursively finding (k-1)-cliques within subgraphs induced by the out-neighbors of each vertex ...
Kunsoo Park, Cheng Long
exaly +3 more sources
List coloring in the absence of two subgraphs [PDF]
Discrete Applied Mathematics, 2013 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Petr A. Golovach, Daniël Paulusma
openaire +3 more sources
On the Ordered List Subgraph Embedding Problems [PDF]
Algorithmica, 2013 In the (parameterized) Ordered List Subgraph Embedding problem (p-OLSE) we are given two graphs $G$ and $H$, each with a linear order defined on its vertices, a function $L$ that associates with every vertex in $G$ a list of vertices in $H$, and a parameter $k$.
Olawale Hassan +3 more
openaire +2 more sources
Algorithms for the quantitative Lock/Key model of cytoplasmic incompatibility
Algorithms for Molecular Biology, 2020 Cytoplasmic incompatibility (CI) relates to the manipulation by the parasite Wolbachia of its host reproduction. Despite its widespread occurrence, the molecular basis of CI remains unclear and theoretical models have been proposed to understand the ...
Tiziana Calamoneri +4 more
doaj +1 more source
Listing Maximal Subgraphs Satisfying Strongly Accessible Properties [PDF]
SIAM Journal on Discrete Mathematics, 2019 Summary: Algorithms for listing the subgraphs satisfying a given property (e.g., being a clique, a cut, a cycle) fall within the general framework of set systems. A set system \((\mathcal{U}, \mathcal{F})\) consists of a ground set \(\mathcal{U}\) (e.g., a network's nodes) and a family \(\mathcal{F} \subseteq 2^{\mathcal{U}}\) of subsets of \(\mathcal ...
Conte A. +3 more
openaire +3 more sources