Maximum Motif Problem in Vertex-Colored Graphs
From MaRDI portal
Publication:3637115
DOI10.1007/978-3-642-02441-2_20zbMath1247.68198OpenAlexW1573571013MaRDI QIDQ3637115
Stéphane Vialette, Guillaume Fertin, Riccardo Dondi
Publication date: 7 July 2009
Published in: Combinatorial Pattern Matching (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-02441-2_20
Graph theory (including graph drawing) in computer science (68R10) 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
Finding and counting vertex-colored subtrees ⋮ Complexity and inapproximability results for balanced connected subgraph problem ⋮ Finding Approximate and Constrained Motifs in Graphs ⋮ Complexity issues in vertex-colored graph pattern matching ⋮ The parameterised complexity of counting connected subgraphs and graph motifs ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ Unnamed Item ⋮ Constrained multilinear detection and generalized graph motifs
Cites Work
- Unnamed Item
- Unnamed Item
- Optimization, approximation, and complexity classes
- Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
- Color-coding
- 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
- Research in Computational Molecular Biology
- On the complexity of comparing evolutionary trees