Complexity issues in vertex-colored graph pattern matching
type: Item
instance of: scholarly article
title: Complexity issues in vertex-colored graph pattern matching
zbMATH Open document ID: 1222.05053
author: Riccardo Dondi
author: Guillaume Fertin
author: Stéphane Vialette
published in: Journal of Discrete Algorithms
publication date: 2011-05-03T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5883236
zbMATH Keywords: graph motifs
zbMATH Keywords: vertex-colored graphs
zbMATH Keywords: algorithmic complexity
zbMATH Keywords: parameterized complexity
MaRDI profile type: Publication
full work available at URL: j.jda.2010.09.002
OpenAlex ID: W2086133268
cites work: Color-coding
cites work: Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
cites work: Fourier meets M\"{o}bius: fast subset convolution
cites work: Complexity results on restricted instances of a paint shop problem for words
cites work: Q3651735
cites work: Maximum Motif Problem in Vertex-Colored Graphs
cites work: Q4393480
cites work: Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
cites work: Analogs & duals of the MAST problem for sequences & trees
cites work: Parametrized complexity theory.
cites work: Parameterized Complexity and Approximability of the SLCS Problem
cites work: Q5572939
cites work: On the complexity of comparing evolutionary trees
cites work: Complexity results on a paint shop problem.
cites work: Algorithm engineering for color-coding with applications to signaling pathway detection
cites work: On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
cites work: Research in Computational Molecular Biology
cites work: An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
cites work: Q5710169
cites work: Optimization, approximation, and complexity classes
cites work: Non deterministic polynomial optimization problems and their approximations
cites work: Q4527015
DOI: 10.1016/J.JDA.2010.09.002
description: scientific article; zbMATH DE number 5883236