Complexity issues in vertex-colored graph pattern matching
From MaRDI portal
Publication:533412
DOI10.1016/j.jda.2010.09.002zbMath1222.05053MaRDI 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
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Deterministic parameterized algorithms for the graph motif problem, Finding approximate and constrained motifs in graphs, Constrained multilinear detection for faster functional motif discovery, Exact exponential algorithms to find tropical connected sets of minimum size, Searching and inferring colorful topological motifs in vertex-colored graphs, Binary jumbled pattern matching on trees and tree-like structures, Parameterized complexity and approximation issues for the colorful components problems, Maximum disjoint paths on edge-colored graphs: approximability and tractability, The \textsc{Maximum Colorful Arborescence} problem: how (computationally) hard can it be?, Algorithms for topology-free and alignment network queries, Some results on more flexible versions of Graph Motif, The graph motif problem parameterized by the structure of the input graph, Fixed-parameter algorithms for scaffold filling, Colourful components in \(k\)-caterpillars and planar graphs, Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size, Algorithmic Aspects of the Maximum Colorful Arborescence Problem
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
