Finding approximate and constrained motifs in graphs

DOI10.1016/J.TCS.2012.08.023zbMath1297.05081OpenAlexW2152084501MaRDI QIDQ390871

Stéphane Vialette, Riccardo Dondi, Guillaume Fertin

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 biologyparameterized complexitygraph motifbiological networks

Mathematics Subject Classification ID

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

Related Items (5)

Deterministic parameterized algorithms for the graph motif problem ⋮ Parameterized complexity and approximation issues for the colorful components problems ⋮ Algorithms for topology-free and alignment network queries ⋮ Exact exponential algorithms to find tropical connected sets of minimum size ⋮ Fixed-parameter algorithms for scaffold filling

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity issues in vertex-colored graph pattern matching
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Non deterministic polynomial optimization problems and their approximations
• Some APX-completeness results for cubic graphs
• The Turing way to parameterized complexity
• Finding and counting vertex-colored subtrees
• Some Results on more Flexible Versions of Graph Motif
• Finding Approximate and Constrained Motifs in Graphs
• On the Kernelization Complexity of Colorful Motifs
• Color-coding
• Collective dynamics of ‘small-world’ networks
• Research in Computational Molecular Biology

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