Space-efficient graph kernelizations

DOI10.1007/978-981-97-2340-9_22MaRDI QIDQ6636090zbMATH OpenFDO

Authors Frank Kammer, Andrej Sajenko

Publication date 12 November 2024

Full work available at URL https://doi.org/10.1007/978-981-97-2340-9_22

zbMATH Keywords

feedback vertex setfull kernelpath contractionspace-efficient algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A 4k^2 kernel for feedback vertex set
• A shortcut to (sun)flowers: kernels in logarithmic space or linear time
• Advice classes of parametrized tractability
• Fast parallel fixed-parameter algorithms via color coding
• Improved algorithms for feedback vertex set problems
• Improved kernel results for some FPT problems based on simple observations
• Linear-time kernelization for feedback vertex set
• Multistage graph problems on a global budget
• On the space and circuit complexity of parameterized problems: classes and completeness
• Optimal In-place Algorithms for Basic Graph Problems
• Parameterized algorithms
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Problems complete for deterministic logarithmic space
• Space-efficient approximation scheme for maximum matching in sparse graphs

Cited in

(1)

• Boundaried kernelization

This page was built for publication: Space-efficient graph kernelizations

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