Maximum Motif Problem in Vertex-Colored Graphs

DOI10.1007/978-3-642-02441-2_20MaRDI QIDQ3637115zbMATH OpenOpenAlexFDO

Authors Riccardo Dondi, Guillaume Fertin, Stéphane Vialette

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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Complexity issues in vertex-colored graph pattern matching
• Finding approximate and constrained motifs in graphs
• Finding and counting vertex-colored subtrees
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• The graph motif problem parameterized by the structure of the input graph

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1518742 (Why is no real title available?)
• Color-coding
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• On the complexity of comparing evolutionary trees
• Optimization, approximation, and complexity classes
• Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
• Research in Computational Molecular Biology
• Research in Computational Molecular Biology
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs

Cited in

(16)

• Constrained multilinear detection and generalized graph motifs
• Finding approximate and constrained motifs in graphs
• Some results on more flexible versions of Graph Motif
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Mathematical Foundations of Computer Science 2005
• Complexity and inapproximability results for balanced connected subgraph problem
• Finding and counting vertex-colored subtrees
• The parameterised complexity of counting connected subgraphs and graph motifs
• Finding and counting vertex-colored subtrees
• Finding approximate and constrained motifs in graphs
• Complexity issues in vertex-colored graph pattern matching
• Probably optimal graph motifs
• Searching and inferring colorful topological motifs in vertex-colored graphs
• Engineering motif search for large motifs
• Some results on more flexible versions of Graph Motif

This page was built for publication: Maximum Motif Problem in Vertex-Colored Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3637115)