Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs

DOI10.1007/978-3-540-73420-8_31zbMath1171.68497OpenAlexW1565474750MaRDI QIDQ5428821

Guillaume Fertin, Danny Hermelin, Michael R. Fellows, Stéphane Vialette

Publication date: 28 November 2007

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-73420-8_31

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Protein sequences, DNA sequences (92D20) Coloring of graphs and hypergraphs (05C15)

Related Items

Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Parameterized complexity of Min-power multicast problems in wireless ad hoc networks ⋮ Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size ⋮ Parameterized Algorithms and Hardness Results for Some Graph Motif Problems ⋮ A Survey on the Complexity of Flood-Filling Games ⋮ Finding and counting vertex-colored subtrees ⋮ On Structural Parameterizations of Graph Motif and Chromatic Number ⋮ Complexity and inapproximability results for balanced connected subgraph problem ⋮ Finding Approximate and Constrained Motifs in Graphs ⋮ Complexity issues in vertex-colored graph pattern matching ⋮ Kernelization hardness of connectivity problems in \(d\)-degenerate graphs ⋮ Upper and lower bounds for finding connected motifs in vertex-colored graphs ⋮ Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs ⋮ On the Kernelization Complexity of Colorful Motifs ⋮ Maximum Motif Problem in Vertex-Colored Graphs ⋮ Searching and inferring colorful topological motifs in vertex-colored graphs ⋮ Tractability and hardness of flood-filling games on trees ⋮ Some results on more flexible versions of Graph Motif ⋮ Constrained multilinear detection and generalized graph motifs