Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}

DOI10.1007/s10878-022-00917-3zbMath1505.90114OpenAlexW4298110488MaRDI QIDQ2091118

Dekel Tsur

Publication date: 31 October 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-022-00917-3

zbMATH Keywords

graph algorithmsparameterized complexitybranching algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• On a generalization of Nemhauser and Trotter's local optimization theorem
• A fixed-parameter algorithm for the vertex cover \(P_3\) problem
• A generalization of Nemhauser and Trotter's local optimization theorem
• On bounded-degree vertex deletion parameterized by treewidth
• Isolation concepts for efficiently enumerating dense subgraphs
• A faster FPT algorithm for 3-path vertex cover
• Kernels for deletion to classes of acyclic digraphs
• Fixed-parameter algorithms for Vertex Cover \(P_3\)
• Polynomial kernels for deletion to classes of acyclic digraphs
• An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
• Faster algorithm for pathwidth one vertex deletion
• On structural parameterizations of the bounded-degree vertex deletion problem
• Parameterized algorithm for 3-path vertex cover
• Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems
• Quick but odd growth of cacti
• Faster parameterized algorithm for pumpkin vertex deletion set
• Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
• A Parameterized Algorithm for Bounded-Degree Vertex Deletion
• Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
• A Quartic Kernel for Pathwidth-One Vertex Deletion
• Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property
• A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion
• A Linear Kernel for Co-Path/Cycle Packing
• A graph‐theoretic generalization of the clique concept

This page was built for publication: Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing}