Maximum Motif Problem in Vertex-Colored Graphs

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

Mathematics Subject Classification ID

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