Complexity issues in vertex-colored graph pattern matching

DOI10.1016/j.jda.2010.09.002zbMath1222.05053OpenAlexW2086133268MaRDI QIDQ533412

Riccardo Dondi, Guillaume Fertin, Stéphane Vialette

Publication date: 3 May 2011

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2010.09.002

zbMATH Keywords

algorithmic complexityparameterized complexitygraph motifsvertex-colored graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (17)

Deterministic parameterized algorithms for the graph motif problem ⋮ Parameterized complexity and approximation issues for the colorful components problems ⋮ The graph motif problem parameterized by the structure of the input graph ⋮ Colourful components in \(k\)-caterpillars and planar graphs ⋮ Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size ⋮ Finding approximate and constrained motifs in graphs ⋮ Binary jumbled pattern matching on trees and tree-like structures ⋮ Constrained multilinear detection for faster functional motif discovery ⋮ The \textsc{Maximum Colorful Arborescence} problem: how (computationally) hard can it be? ⋮ Algorithmic Aspects of the Maximum Colorful Arborescence Problem ⋮ Maximum disjoint paths on edge-colored graphs: approximability and tractability ⋮ 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 ⋮ Heuristic Algorithms for the Maximum Colorful Subtree Problem ⋮ Searching and inferring colorful topological motifs in vertex-colored graphs ⋮ Some results on more flexible versions of Graph Motif

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithm engineering for color-coding with applications to signaling pathway detection
• Non deterministic polynomial optimization problems and their approximations
• Optimization, approximation, and complexity classes
• Complexity results on a paint shop problem.
• Parametrized complexity theory.
• Complexity results on restricted instances of a paint shop problem for words
• Parameterized Complexity and Approximability of the SLCS Problem
• Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
• Fourier meets M\"{o}bius: fast subset convolution
• Maximum Motif Problem in Vertex-Colored Graphs
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• Color-coding
• Analogs & duals of the MAST problem for sequences & trees
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
• Research in Computational Molecular Biology
• On the complexity of comparing evolutionary trees

This page was built for publication: Complexity issues in vertex-colored graph pattern matching