Faster algorithms for finding and counting subgraphs
DOI10.1016/j.jcss.2011.10.001zbMath1246.05149WikidataQ60488486 ScholiaQ60488486MaRDI QIDQ439930
Venkatesh Raman, Daniel Lokshtanov, Saket Saurabh, Fedor V. Fomin, 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
68Q25: Analysis of algorithms and problem complexity
05C05: Trees
68R10: Graph theory (including graph drawing) in computer science
05C30: Enumeration in graph theory
05C85: Graph algorithms (graph-theoretic aspects)
68W20: Randomized algorithms
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
- The vertex separation number of a graph equals its path-width
- Treewidth. Computations and approximations
- Counting \(H-\)colorings of partial \(k-\)trees
- Trimmed Moebius inversion and graphs of bounded degree
- Narrow sieves for parameterized paths and packings
- Balanced families of perfect hash functions and their applications
- Faster Algebraic Algorithms for Path and Packing Problems
- Divide-and-Color
- Limits and Applications of Group Algebras for Parameterized Problems
- Counting Paths and Packings in Halves
- Computational aspects of the Mobius transformation of graphs
- Color-coding
- The Parameterized Complexity of Counting Problems
- Finding, minimizing, and counting weighted subgraphs
- Counting Subgraphs via Homomorphisms