Faster algorithms for finding and counting subgraphs
Publication:439930
DOI10.1016/j.jcss.2011.10.001zbMath1246.05149OpenAlexW2089369802WikidataQ60488486 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
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
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