Deterministic parameterized algorithms for the graph motif problem

DOI10.1016/J.DAM.2016.04.026MaRDI QIDQ313814zbMATH OpenOpenAlexFDO

Authors Hadas Shachnai, Meirav Zehavi, Ron Y. Pinter

Publication date 12 September 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2016.04.026

zbMATH Keywords

graph motifguiding treeparameterized algorithmrepresentative family

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Recommendations

• Deterministic parameterized algorithms for the graph motif problem
• The graph motif problem parameterized by the structure of the input graph
• Finding and counting vertex-colored subtrees
• The graph motif problem parameterized by the structure of the input graph
• Parameterized algorithms for the module motif problem

Cites work

• scientific article; zbMATH DE number 5047784 (Why is no real title available?)
• Algorithms for topology-free and alignment network queries
• Color-coding
• Complexity issues in vertex-colored graph pattern matching
• Constrained multilinear detection for faster functional motif discovery
• Efficient computation of representative sets with applications in parameterized and exact algorithms
• Finding and counting vertex-colored subtrees
• Finding approximate and constrained motifs in graphs
• Multiplying matrices faster than coppersmith-winograd
• Narrow sieves for parameterized paths and packings
• On the Kernelization Complexity of Colorful Motifs
• Partial information network queries
• Representative families: a unified tradeoff-based approach
• Representative sets of product families
• Some results on more flexible versions of Graph Motif
• Upper and lower bounds for finding connected motifs in vertex-colored graphs

Cited in

(8)

• Constrained multilinear detection for faster functional motif discovery
• Quasipolynomial representation of transversal matroids with applications in parameterized complexity
• Parameterized algorithms for the module motif problem
• Deterministic parameterized algorithms for the graph motif problem
• Graph motif problems parameterized by dual
• Searching and inferring colorful topological motifs in vertex-colored graphs
• Engineering motif search for large motifs
• Parameterized algorithms for module motif

This page was built for publication: Deterministic parameterized algorithms for the graph motif problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q313814)