On the Kernelization Complexity of Colorful Motifs
From MaRDI portal
Publication:3058688
DOI10.1007/978-3-642-17493-3_4zbMath1309.68143OpenAlexW1561121869MaRDI QIDQ3058688
Geevarghese Philip, Chintan Rao H., Neeldhara Misra, Radheshyam Balasundaram, M. S. Ramanujan, Venkata Koppula, Abhimanyu M. Ambalath
Publication date: 7 December 2010
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-17493-3_4
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics, Deterministic parameterized algorithms for the graph motif problem, Parameterized algorithms for the module motif problem, Algorithmic Aspects of Disjunctive Domination in Graphs, The graph motif problem parameterized by the structure of the input graph, Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size, Finding approximate and constrained motifs in graphs, Binary jumbled pattern matching on trees and tree-like structures, Finding and counting vertex-colored subtrees, Graph Motif Problems Parameterized by Dual, On Structural Parameterizations of Graph Motif and Chromatic Number, Finding Approximate and Constrained Motifs in Graphs, Algorithms for topology-free and alignment network queries, Exact exponential algorithms to find tropical connected sets of minimum size, Partial information network queries, Kernelization hardness of connectivity problems in \(d\)-degenerate graphs, Turing kernelization for finding long paths in graph classes excluding a topological minor, Algorithmic aspects of \(b\)-disjunctive domination in graphs, On the Kernelization Complexity of Colorful Motifs, Turing kernelization for finding long paths and cycles in restricted graph classes, On some FPT problems without polynomial Turing compressions, Some results on more flexible versions of Graph Motif
Cites Work
- Unnamed Item
- Unnamed Item
- On problems without polynomial kernels
- Competing provers yield improved Karp-Lipton collapse results
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- On the Kernelization Complexity of Colorful Motifs
- Finding and Counting Vertex-Colored Subtrees
- Incompressibility through Colors and IDs
- Kernel Bounds for Disjoint Cycles and Disjoint Paths
- Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
- Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
