Finding approximate and constrained motifs in graphs

DOI10.1016/J.TCS.2012.08.023zbMATH Open1297.05081OpenAlexW2152084501MaRDI QIDQ390871FDOQ390871

Authors Riccardo Dondi, Guillaume Fertin, Stéphane Vialette

Publication date 9 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.08.023

zbMATH Keywords

algorithmscomputational complexitycomputational biologygraph motifparameterized complexitybiological networks

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Systems biology, networks (92C42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Computational methods for problems pertaining to biology (92-08)

Recommendations

• Finding approximate and constrained motifs in graphs
• Maximum Motif Problem in Vertex-Colored Graphs
• Complexity issues in vertex-colored graph pattern matching
• Some results on more flexible versions of Graph Motif
• Some results on more flexible versions of Graph Motif

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Collective dynamics of `small-world' networks
• Color-coding
• Complexity issues in vertex-colored graph pattern matching
• Finding and counting vertex-colored subtrees
• Finding approximate and constrained motifs in graphs
• Non deterministic polynomial optimization problems and their approximations
• On the Kernelization Complexity of Colorful Motifs
• Research in Computational Molecular Biology
• Some APX-completeness results for cubic graphs
• Some results on more flexible versions of Graph Motif
• The Turing way to parameterized complexity
• Upper and lower bounds for finding connected motifs in vertex-colored graphs

Cited in

(13)

• Some results on more flexible versions of Graph Motif
• Algorithms for topology-free and alignment network queries
• A uniform random graph model for directed acyclic networks and its effect on motif-finding
• Searching and inferring colorful topological motifs in vertex-colored graphs
• Maximum Motif Problem in Vertex-Colored Graphs
• Some results on more flexible versions of Graph Motif
• Fixed-parameter algorithms for scaffold filling
• Complexity issues in vertex-colored graph pattern matching
• Deterministic parameterized algorithms for the graph motif problem
• Engineering Motif Search for Large Graphs
• Finding approximate and constrained motifs in graphs
• Parallel Discovery of Top-k Weighted Motifs in Large Graphs
• Exact exponential algorithms to find tropical connected sets of minimum size

This page was built for publication: Finding approximate and constrained motifs in graphs

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