Some results on more flexible versions of Graph Motif

DOI10.1007/s00224-014-9564-6zbMath1316.05048arXiv1202.5184OpenAlexW3102729840MaRDI QIDQ2354588

Florian Sikora, Romeo Rizzi

Publication date: 20 July 2015

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1202.5184

zbMATH Keywords

computational complexitycomputational biologybiological networksGraph Motif problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Systems biology, networks (92C42)

Related Items

Deterministic parameterized algorithms for the graph motif problem ⋮ The \textsc{Maximum Colorful Arborescence} problem: how (computationally) hard can it be?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Constrained multilinear detection for faster functional motif discovery
• Complexity issues in vertex-colored graph pattern matching
• Partitive hypergraphs
• Finding and counting vertex-colored subtrees
• New examples of non–slice, algebraically slice knots
• Probably optimal graph motifs
• Finding Approximate and Constrained Motifs in Graphs
• On the Kernelization Complexity of Colorful Motifs
• Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
• Decomposition of Directed Graphs
• On Syntactic versus Computational Views of Approximability
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Algorithm Theory - SWAT 2004
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs