On the Kernelization Complexity of Colorful Motifs

DOI10.1007/978-3-642-17493-3_4MaRDI QIDQ3058688zbMATH OpenOpenAlexFDO

Authors Abhimanyu M. Ambalath, Radheshyam Balasundaram, Chintan Rao H., Venkata Koppula, Neeldhara Misra, Geevarghese Philip, M. S. Ramanujan

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• \(k\)-colored kernels
• Searching and inferring colorful topological motifs in vertex-colored graphs
• Kernelization lower bounds through colors and IDs
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
• On the parameterized complexity of colorful components and related problems
• scientific article; zbMATH DE number 2186880
• On the parameterized intractability of motif search problems
• Upper and lower bounds for finding connected motifs in vertex-colored graphs

Cites work

• \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves
• Competing provers yield improved Karp-Lipton collapse results
• Finding and counting vertex-colored subtrees
• scientific article; zbMATH DE number 5485524 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Incompressibility through Colors and IDs
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
• On problems without polynomial kernels
• On the Kernelization Complexity of Colorful Motifs
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs

Cited in

(23)

• Finding and counting vertex-colored subtrees
• Partial information network queries
• On some FPT problems without polynomial Turing compressions
• Algorithms for topology-free and alignment network queries
• Turing kernelization for finding long paths in graph classes excluding a topological minor
• Some results on more flexible versions of Graph Motif
• The graph motif problem parameterized by the structure of the input graph
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• Exact exponential algorithms to find a tropical connected set of minimum size
• On structural parameterizations of graph motif and chromatic number
• Finding approximate and constrained motifs in graphs
• On the Kernelization Complexity of Colorful Motifs
• Deterministic parameterized algorithms for the graph motif problem
• Algorithmic aspects of disjunctive domination in graphs
• Parameterized algorithms for the module motif problem
• Finding approximate and constrained motifs in graphs
• Graph motif problems parameterized by dual
• Exact exponential algorithms to find tropical connected sets of minimum size
• Polynomial Turing compressions for some graph problems parameterized by modular-width
• Polynomial Turing compressions for some graph problems parameterized by modular-width
• Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
• Algorithmic aspects of \(b\)-disjunctive domination in graphs
• Binary jumbled pattern matching on trees and tree-like structures

This page was built for publication: On the Kernelization Complexity of Colorful Motifs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3058688)