Complexity issues in vertex-colored graph pattern matching
From MaRDI portal
Publication:533412
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
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
