Solving Co-Path/Cycle Packing and Co-Path Packing faster than 3ᵏ

DOI10.1016/J.IC.2026.105406MaRDI QIDQ6841906zbMATH OpenFDO

Authors Yuxi Liu, Mingyu Xiao

Publication date 20 March 2026

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2026.105406

zbMATH Keywords

Co-Path PackingCo-Path/Cycle Packingcut \& countgraph algorithmsparameterized algorithmspath decomposition

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A faster FPT algorithm for 3-path vertex cover
• A fixed-parameter algorithm for the vertex cover P₃ problem
• A generalization of Nemhauser and Trotter's local optimization theorem
• A generic convolution algorithm for join operations on tree decompositions
• A graph‐theoretic generalization of the clique concept
• A linear kernel for co-path/cycle packing
• A parameterized algorithm for bounded-degree vertex deletion
• Exact algorithms via monotone local search
• Exact exponential algorithms.
• Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• Generating Faster Algorithms for d-Path Vertex Cover
• Improved upper bounds for vertex cover
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• On a generalization of Nemhauser and Trotter's local optimization theorem
• On two techniques of combining branching and treewidth
• Parameterized algorithm for 3-path vertex cover
• Parameterized algorithms
• Randomized parameterized algorithms for P₂-packing and co-path packing problems
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

This page was built for publication: Solving Co-Path/Cycle Packing and Co-Path Packing faster than \(3^k\)

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