Constrained multilinear detection and generalized graph motifs
From MaRDI portal
Publication:262282
DOI10.1007/s00453-015-9981-1zbMath1336.68115arXiv1209.1082OpenAlexW2073438136WikidataQ59473175 ScholiaQ59473175MaRDI QIDQ262282
Andreas Björklund, Petteri Kaski, Łukasz Kowalik
Publication date: 29 March 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1209.1082
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Polynomials over finite fields (11T06) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (19)
Narrow sieves for parameterized paths and packings ⋮ The graph motif problem parameterized by the structure of the input graph ⋮ Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Unnamed Item ⋮ Graph Motif Problems Parameterized by Dual ⋮ Parameterized algorithms for list \(K\)-cycle ⋮ Clearing directed subgraphs by mobile agents. Variations on covering with paths ⋮ Efficient indexes for jumbled pattern matching with constant-sized alphabet ⋮ Exact exponential algorithms to find tropical connected sets of minimum size ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The maximum binary tree problem ⋮ Fine-grained complexity of safety verification ⋮ The Maximum Colorful Arborescence problem parameterized by the structure of its color hierarchy graph ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ Unnamed Item ⋮ Univariate ideal membership parameterized by rank, degree, and number of generators ⋮ On the Complexity of Bounded Context Switching. ⋮ Parameterized Pre-Coloring Extension and List Coloring Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Constrained multilinear detection for faster functional motif discovery
- Upper and lower bounds for finding connected motifs in vertex-colored graphs
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- A probabilistic remark on algebraic program testing
- Narrow sieves for parameterized paths and packings
- Probably optimal graph motifs
- Finding Approximate and Constrained Motifs in Graphs
- Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
- Faster Algebraic Algorithms for Path and Packing Problems
- Finding and Counting Vertex-Colored Subtrees
- Maximum Motif Problem in Vertex-Colored Graphs
- Limits and Applications of Group Algebras for Parameterized Problems
- Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- On Problems as Hard as CNF-SAT
- Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
This page was built for publication: Constrained multilinear detection and generalized graph motifs
