Results 11 to 20 of about 564 (166)
Listing maximal H-free subgraphs
Discrete Applied MathematicszbMATH Open Web Interface contents unavailable due to conflicting licenses.
Conte, Alessio +4 more
openaire +5 more sources
Efficient orbit-aware triad and quad census in directed and undirected graphs
Applied Network Science, 2017 The prevalence of select substructures is an indicator of network effects in applications such as social network analysis and systems biology. Moreover, subgraph statistics are pervasive in stochastic network models, and they need to be assessed ...
Mark Ortmann, Ulrik Brandes
doaj +2 more sources
Flips in colorful triangulations [PDF]
Journal of Computational GeometryThe associahedron is the graph $\mathcal{G}_N$ that has as nodes all triangulations of a convex $N$-gon, and an edge between any two triangulations that differ in a flip operation.
Rohan Acharya +2 more
doaj +4 more sources
Listing Induced Steiner Subgraphs as a Compact Way to Discover Steiner Trees in Graphs. [PDF]
, 2019 This paper investigates induced Steiner subgraphs as a variant of the classical Steiner trees, so as to compactly represent the (exponentially many) Steiner trees sharing the same underlying induced subgraph. We prove that the enumeration of all (inclusion-minimal) induced Steiner subgraphs is harder than the well-known Hypergraph Transversal ...
Conte, Alessio +5 more
openaire +5 more sources
Efficient frequent connected subgraph mining in graphs of bounded treewidth
, 2022 S.520-535The frequent connected subgraph mining problem, i.e., the problem of listing all connected graphs that are subgraph isomorphic to at least a certain number of transaction graphs of a database, cannot be solved in output polynomial time in the ...
Ramon, J., Horvath, Tamas
core +2 more sources
Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph
SIAM Journal on Discrete Mathematics, 2022 Accepted manuscript, see DOI for journal ...
Sepehr Hajebi, Yanjia Li, Sophie Spirkl
openaire +3 more sources
KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs [PDF]
, 2020 The problem of finding densest subgraphs has received increasing attention in recent years finding applications in biology, finance, as well as social network analysis.
Chan, TH, SUN, B, Danisch, M, Sozio, M
core +3 more sources
Lower Bounds for Induced Cycle Detection in Distributed Computing [PDF]
, 2021 The distributed subgraph detection asks, for a fixed graph H, whether the n-node input graph contains H as a subgraph or not. In the standard CONGEST model of distributed computing, the complexity of clique/cycle detection and listing has received a lot ...
Le Gall, François, Miyamoto, Masayuki
core +1 more source
Efficient Subgraph Computing on Large-Scale Graphs
, 2022 The problem of efficiently computing subgraphs has received much attention from the database research community. In this thesis, we study important problem of efficient graph analysis at a large scale.
Yu, Michael
core +1 more source
Listing Maximal Subgraphs in Strongly Accessible Set Systems
CoRR, 2018 Algorithms for listing the subgraphs satisfying a given property (e.g.,being a clique, a cut, a cycle, etc.) fall within the general framework of set systems. A set system (U, F) uses a ground set U (e.g., the network nodes) and an indicator F, subset of 2^U, of which subsets of U have the required property.
Alessio Conte +3 more
openaire +2 more sources