Polynomial Turing compressions for some graph problems parameterized by modular-width

DOI10.1007/978-3-031-49190-0_9MaRDI QIDQ6591463

Weidong Luo

Publication date: 22 August 2024

zbMATH Keywords

fixed parameter tractableTuring kernelTuring compressionmodular-widthstructural graph parameter

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fundamentals of parameterized complexity
• A survey of the algorithmic aspects of modular decomposition
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Turing kernelization for finding long paths and cycles in restricted graph classes
• Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
• Parameterized computational complexity of finding small-diameter subgraphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• On some FPT problems without polynomial Turing compressions
• A hierarchy of polynomial kernels
• Turing kernelization for finding long paths in graph classes excluding a topological minor
• A completeness theory for polynomial (Turing) kernelization
• Fast exact algorithms for some connectivity problems parameterized by clique-width
• A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
• Parameterized Algorithms for Modular-Width
• On the Kernelization Complexity of Colorful Motifs
• On Problems without Polynomial Kernels (Extended Abstract)
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Faster Algorithms on Branch and Clique Decompositions
• Kernelization
• Kernelization Lower Bounds by Cross-Composition
• Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
• Parameterized Algorithms
• Independent set reconfiguration parameterized by modular-width

This page was built for publication: Polynomial Turing compressions for some graph problems parameterized by modular-width

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