Finding Approximate and Constrained Motifs in Graphs

DOI10.1007/978-3-642-21458-5_33zbMath1339.92025OpenAlexW2179833021MaRDI QIDQ3011870

Riccardo Dondi, Stéphane Vialette, Guillaume Fertin

Publication date: 29 June 2011

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-21458-5_33

zbMATH Keywords

NP-hardmetabolic network analysisconstrained graph motif

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Systems biology, networks (92C42)

Related Items

Parameterized algorithms for the module motif problem ⋮ Improved Parameterized Algorithms for Network Query Problems ⋮ Finding approximate and constrained motifs in graphs ⋮ Improved parameterized algorithms for network query problems ⋮ Binary jumbled pattern matching on trees and tree-like structures ⋮ Constrained multilinear detection for faster functional motif discovery ⋮ Some results on more flexible versions of Graph Motif ⋮ Constrained multilinear detection and generalized graph motifs

Cites Work

• Unnamed Item
• Non deterministic polynomial optimization problems and their approximations
• Some APX-completeness results for cubic graphs
• The Turing way to parameterized complexity
• On the Kernelization Complexity of Colorful Motifs
• Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
• Finding and Counting Vertex-Colored Subtrees
• Maximum Motif Problem in Vertex-Colored Graphs
• Color-coding
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
• Research in Computational Molecular Biology
• Research in Computational Molecular Biology