Faster algorithms for finding and counting subgraphs
From MaRDI portal
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Enumeration in graph theory (05C30)
Recommendations
Cites work
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
- Balanced families of perfect hash functions and their applications
- Color-coding
- Computational aspects of the Mobius transformation of graphs
- Counting Paths and Packings in Halves
- Counting Subgraphs via Homomorphisms
- Counting \(H-\)colorings of partial \(k-\)trees
- Counting graph homomorphisms
- Divide-and-Color
- Faster Algebraic Algorithms for Path and Packing Problems
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Finding, minimizing, and counting weighted subgraphs
- Improved algorithms for path, matching, and packing problems
- Limits and Applications of Group Algebras for Parameterized Problems
- Narrow sieves for parameterized paths and packings
- The Parameterized Complexity of Counting Problems
- The vertex separation number of a graph equals its path-width
- Treewidth. Computations and approximations
- Trimmed Moebius inversion and graphs of bounded degree
Cited in
(37)- Counting Answers to Existential Questions
- scientific article; zbMATH DE number 7561323 (Why is no real title available?)
- Counting subgraphs via homomorphisms
- Efficient algorithms for subgraph listing
- scientific article; zbMATH DE number 7650232 (Why is no real title available?)
- Detecting and counting small pattern graphs
- Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
- Stable matching games: manipulation via subgraph isomorphism
- Finding and counting small induced subgraphs efficiently
- Planar subgraph isomorphism revisited
- Improved parameterized algorithms for network query problems
- Randomized parameterized algorithms for the kidney exchange problem
- Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
- Tensor network complexity of multilinear maps
- A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
- Faster Subgraph Counting in Sparse Graphs
- Approximately Counting Embeddings into Random Graphs
- Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
- Counting connected subgraphs with maximum-degree-aware sieving
- Beating treewidth for average-case subgraph isomorphism
- Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
- Homomorphisms are a good basis for counting small subgraphs
- Finding even subgraphs even faster
- Approximately counting embeddings into random graphs
- On linear algebraic algorithms for the subgraph matching problem and its variants
- Clearing directed subgraphs by mobile agents. Variations on covering with paths
- Faster algorithms for counting subgraphs in sparse graphs
- Exact weight subgraphs and the \(k\)-sum conjecture
- scientific article; zbMATH DE number 1929947 (Why is no real title available?)
- Improved parameterized algorithms for network query problems
- Recognizing small subgraphs
- On proving parameterized size lower bounds for multilinear algebraic models
- Sublinear-time algorithms for counting star subgraphs via edge sampling
- scientific article; zbMATH DE number 910922 (Why is no real title available?)
- A slice theoretic approach for embedding problems on digraphs
- Subtree isomorphism revisited
- Fixed-parameter tractability of satisfying beyond the number of variables
This page was built for publication: Faster algorithms for finding and counting subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q439930)
