Complexity issues in vertex-colored graph pattern matching
DOI10.1016/J.JDA.2010.09.002zbMATH Open1222.05053OpenAlexW2086133268MaRDI QIDQ533412FDOQ533412
Authors: 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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Introduction to algorithms.
- On the complexity of comparing evolutionary trees
- Optimization, approximation, and complexity classes
- Parametrized complexity theory.
- Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
- Maximum Motif Problem in Vertex-Colored Graphs
- Color-coding
- Title not available (Why is that?)
- Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
- Fourier meets M\"{o}bius: fast subset convolution
- Algorithm engineering for color-coding with applications to signaling pathway detection
- Non deterministic polynomial optimization problems and their approximations
- Complexity results on a paint shop problem.
- Complexity results on restricted instances of a paint shop problem for words
- On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
- Analogs & duals of the MAST problem for sequences & trees
- Parameterized Complexity and Approximability of the SLCS Problem
- Research in Computational Molecular Biology
Cited In (24)
- Approximation hardness of the cross-species conserved active modules detection problem
- Algorithmic aspects of the maximum colorful arborescence problem
- Finding approximate and constrained motifs in graphs
- Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
- Constrained multilinear detection for faster functional motif discovery
- The \textsc{Maximum Colorful Arborescence} problem: how (computationally) hard can it be?
- Maximum disjoint paths on edge-colored graphs: approximability and tractability
- Exact exponential algorithms to find a tropical connected set of minimum size
- Finding supported paths in heterogeneous networks
- Upper and lower bounds for finding connected motifs in vertex-colored graphs
- Heuristic algorithms for the maximum colorful subtree problem
- Finding and counting vertex-colored subtrees
- Deterministic parameterized algorithms for the graph motif problem
- Finding approximate and constrained motifs in graphs
- Colourful components in \(k\)-caterpillars and planar graphs
- Probably optimal graph motifs
- Searching and inferring colorful topological motifs in vertex-colored graphs
- Binary jumbled pattern matching on trees and tree-like structures
- Maximum Motif Problem in Vertex-Colored Graphs
- Algorithms for topology-free and alignment network queries
- Fixed-parameter algorithms for scaffold filling
- Some results on more flexible versions of Graph Motif
- The graph motif problem parameterized by the structure of the input graph
- Exact exponential algorithms to find tropical connected sets of minimum size
This page was built for publication: Complexity issues in vertex-colored graph pattern matching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q533412)
