The graph motif problem parameterized by the structure of the input graph
From MaRDI portal
Publication:2403795
DOI10.1016/j.dam.2016.11.016zbMath1369.05195arXiv1503.05110OpenAlexW2758517243MaRDI QIDQ2403795
Édouard Bonnet, Florian Sikora
Publication date: 12 September 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1503.05110
Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Systems biology, networks (92C42)
Related Items (10)
The balanced connected subgraph problem for geometric intersection graphs ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ Structural parameterization of cluster deletion ⋮ FPT and kernelization algorithms for the induced tree problem ⋮ Graph Motif Problems Parameterized by Dual ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ The balanced connected subgraph problem ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Constrained multilinear detection and generalized graph motifs
- Fundamentals of parameterized complexity
- Constrained multilinear detection for faster functional motif discovery
- Complexity issues in vertex-colored graph pattern matching
- Improved upper bounds for vertex cover
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- Upper and lower bounds for finding connected motifs in vertex-colored graphs
- The complexity ecology of parameters: An illustration using bounded max leaf number
- Which problems have strongly exponential complexity?
- Algorithmic meta-theorems for restrictions of treewidth
- The Turing way to parameterized complexity
- A golden ratio parameterized algorithm for cluster editing
- Finding and counting vertex-colored subtrees
- Algorithms for topology-free and alignment network queries
- Tight lower bounds for certain parameterized NP-hard problems
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS
- New Races in Parameterized Algorithmics
- Deterministic Parameterized Algorithms for the Graph Motif Problem
- On the Kernelization Complexity of Colorful Motifs
- Spanning Trees with Many Leaves
- Known Algorithms for Edge Clique Cover are Probably Optimal
- On the hardness of approximating minimization problems
- Kernelization Lower Bounds by Cross-Composition
- Engineering Motif Search for Large Graphs
- Data reduction and exact algorithms for clique cover
- Parameterized Algorithms
- Graph-Theoretic Concepts in Computer Science
- On the complexity of \(k\)-SAT
This page was built for publication: The graph motif problem parameterized by the structure of the input graph
