Finding and counting vertex-colored subtrees

DOI10.1007/s00453-011-9600-8zbMath1263.05029arXiv1002.1880OpenAlexW2763029945MaRDI QIDQ1949738

Florian Sikora, Sylvain Guillemot

Publication date: 16 May 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1002.1880

zbMATH Keywords

parameterized complexitybiological networksvertex-colored graphspattern matching in graphs

Mathematics Subject Classification ID

Applications of graph theory (05C90) 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) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (21)

On finding rainbow and colorful paths ⋮ Deterministic parameterized algorithms for the graph motif problem ⋮ Parameterized algorithms for the module motif problem ⋮ The graph motif problem parameterized by the structure of the input graph ⋮ Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size ⋮ Improved Parameterized Algorithms for Network Query Problems ⋮ Finding approximate and constrained motifs in graphs ⋮ Improved parameterized algorithms for network query problems ⋮ Unnamed Item ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts ⋮ Algorithms for topology-free and alignment network queries ⋮ Exact exponential algorithms to find tropical connected sets of minimum size ⋮ The parameterised complexity of counting connected subgraphs and graph motifs ⋮ Partial information network queries ⋮ Fixed-parameter algorithms for scaffold filling ⋮ The maximum binary tree problem ⋮ Unnamed Item ⋮ Searching and inferring colorful topological motifs in vertex-colored graphs ⋮ Some results on more flexible versions of Graph Motif

Uses Software

• GraMoFoNe

Cites Work

• Unnamed Item
• Algorithm engineering for color-coding with applications to signaling pathway detection
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Dynamic programming meets the principle of inclusion and exclusion
• On the Kernelization Complexity of Colorful Motifs
• Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
• Fourier meets M\"{o}bius: fast subset convolution
• Finding and Counting Vertex-Colored Subtrees
• Maximum Motif Problem in Vertex-Colored Graphs
• Color-coding
• The Parameterized Complexity of Counting Problems
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs

This page was built for publication: Finding and counting vertex-colored subtrees