Results 1 to 10 of about 6,506,935 (189)
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
Matched Filters for Noisy Induced Subgraph Detection. [PDF]
IEEE Trans Pattern Anal Mach Intell, 2020 The problem of finding the vertex correspondence between two noisy graphs with different number of vertices where the smaller graph is still large has many applications in social networks, neuroscience, and computer vision.
Sussman DL +3 more
europepmc +3 more sources
Identifying HIV-induced subgraph patterns in brain networks with side information. [PDF]
Brain Inform, 2015 Investigating brain connectivity networks for neurological disorder identification has attracted great interest in recent years, most of which focus on the graph representation alone.
Cao B, Kong X, Zhang J, Yu PS, Ragin AB.
europepmc +2 more sources
Induced Subgraph Saturated Graphs
Theory and Applications of Graphs, 2016 A graph $G$ is said to be \emph{$H$-saturated} if $G$ contains no subgraph isomorphic to $H$ but the addition of any edge between non-adjacent vertices in $G$ creates one.
Craig Tennenhouse
doaj +2 more sources
Learning Rule-Induced Subgraph Representations for Inductive Relation Prediction [PDF]
Neural Information Processing SystemsInductive relation prediction (IRP) -- where entities can be different during training and inference -- has shown great power for completing evolving knowledge graphs.
Tianyu Liu +4 more
openalex +2 more sources
On the complexity of various parameterizations of common induced subgraph isomorphism [PDF]
Theoretical Computer Science, 2017 Faisal N. Abu-Khzam +2 more
openalex +3 more sources
QuACS: Variational Quantum Algorithm for Coalition Structure Generation in Induced Subgraph Games [PDF]
ACM International Conference on Computing Frontiers, 2023 Coalition Structure Generation (CSG) is an NP-Hard problem in which agents are partitioned into mutually exclusive groups to maximize their social welfare. In this work, we propose QuACS, a novel hybrid quantum-classical algorithm for Coalition Structure
Supreeth Mysore Venkatesh +2 more
semanticscholar +1 more source
On induced subgraph of Cartesian product of paths [PDF]
Journal of Graph Theory, 2023 Chung et al. constructed an induced subgraph of the hypercube Q n ${Q}^{n}$ with α( Q n ) + 1 $\alpha ({Q}^{n})+1$ vertices and with maximum degree smaller than ⌈ n ⌉ $\lceil \sqrt{n}\rceil $ .
Jiasheng Zeng, Xinmin Hou
semanticscholar +1 more source
Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph [PDF]
SIAM Journal on Discrete Mathematics, 2021 For a positive integer $r$ and graphs $G$ and $H$, we denote by $G+H$ the disjoint union of $G$ and $H$, and by $rH$ the union of $r$ mutually disjoint copies of $H$. Also, we say $G$ is $H$-free if $H$ is not isomorphic to an induced subgraph of $G$. We
Sepehr Hajebi, Yanjia Li, S. Spirkl
semanticscholar +1 more source
An induced subgraph of the Hamming graph with maximum degree 1 [PDF]
Journal of Graph Theory, 2021 For every graph G $G$ , let α ( G ) $\alpha (G)$ denote its independence number. What is the minimum of the maximum degree of an induced subgraph of G $G$ with α ( G ) + 1 $\alpha (G)+1$ vertices? We study this question for the n $n$ ‐dimensional Hamming
Vincent Tandya
semanticscholar +1 more source