Constrained multilinear detection for faster functional motif discovery

DOI10.1016/j.ipl.2012.08.008zbMath1248.68583arXiv1206.3483MaRDI QIDQ456168

Ioannis Koutis

Publication date: 23 October 2012

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithms; randomized algorithms; parameterized algorithms

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C85: Graph algorithms (graph-theoretic aspects)

68W20: Randomized algorithms

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle, Constrained multilinear detection and generalized graph motifs, Deterministic parameterized algorithms for the graph motif problem, Parameterized algorithms for the module motif problem, Exact exponential algorithms to find tropical connected sets of minimum size, Partial information network queries, Univariate ideal membership parameterized by rank, degree, and number of generators, Algorithms for topology-free and alignment network queries, Some results on more flexible versions of Graph Motif, The graph motif problem parameterized by the structure of the input graph, Improved parameterized algorithms for network query problems, Improved Parameterized Algorithms for Network Query Problems

Cites Work

• Complexity issues in vertex-colored graph pattern matching
• Upper and lower bounds for finding connected motifs in vertex-colored graphs
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Finding Approximate and Constrained Motifs in Graphs
• Faster Algebraic Algorithms for Path and Packing Problems
• Finding and Counting Vertex-Colored Subtrees
• Limits and Applications of Group Algebras for Parameterized Problems