Faster algorithms for finding and counting subgraphs
DOI10.1016/J.JCSS.2011.10.001zbMATH Open1246.05149DBLPjournals/jcss/FominLRSR12OpenAlexW2089369802WikidataQ60488486 ScholiaQ60488486MaRDI QIDQ439930FDOQ439930
Authors: Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, B. V. Raghavendra Rao 
Publication date: 17 August 2012
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2011.10.001
Recommendations
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)
Cites Work
- Counting graph homomorphisms
- Narrow sieves for parameterized paths and packings
- Improved algorithms for path, matching, and packing problems
- Faster Algebraic Algorithms for Path and Packing Problems
- Limits and Applications of Group Algebras for Parameterized Problems
- Title not available (Why is that?)
- Color-coding
- Finding, minimizing, and counting weighted subgraphs
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Treewidth. Computations and approximations
- Counting Paths and Packings in Halves
- The vertex separation number of a graph equals its path-width
- Computational aspects of the Mobius transformation of graphs
- Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
- The Parameterized Complexity of Counting Problems
- Divide-and-Color
- Counting Subgraphs via Homomorphisms
- Counting \(H-\)colorings of partial \(k-\)trees
- Trimmed Moebius inversion and graphs of bounded degree
- Balanced families of perfect hash functions and their applications
Cited In (37)
- Title not available (Why is that?)
- Counting subgraphs via homomorphisms
- Efficient algorithms for subgraph listing
- Title not available (Why is that?)
- Detecting and counting small pattern graphs
- Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
- Planar subgraph isomorphism revisited
- Stable matching games: manipulation via subgraph isomorphism
- Finding and counting small induced subgraphs efficiently
- Improved parameterized algorithms for network query problems
- Randomized parameterized algorithms for the kidney exchange problem
- Tensor network complexity of multilinear maps
- Faster Subgraph Counting in Sparse Graphs
- A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
- Approximately Counting Embeddings into Random Graphs
- Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
- 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
- Title not available (Why is that?)
- Recognizing small subgraphs
- On proving parameterized size lower bounds for multilinear algebraic models
- Improved parameterized algorithms for network query problems
- Title not available (Why is that?)
- Sublinear-time algorithms for counting star subgraphs via edge sampling
- A slice theoretic approach for embedding problems on digraphs
- Subtree isomorphism revisited
- Counting Answers to Existential Questions
- 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)
