Packing arc-disjoint cycles in oriented graphs

DOI10.1016/J.JCSS.2024.103530MaRDI QIDQ6126480zbMATH OpenOpenAlexFDO

Authors Jasine Babu, Ajay Saju Jacob, R. Krithika, Deepak Rajendraprasad

Publication date 9 April 2024

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2024.103530

zbMATH Keywords

arc-disjoint cyclesErdös-Pósa-type theoremskernelsparameterized algorithms

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• A simplified NP-complete satisfiability problem
• An application of simultaneous diophantine approximation in combinatorial optimization
• An improved kernelization algorithm for \(r\)-set packing
• Approximation algorithms and hardness results for cycle packing problems
• Color-coding
• Cycles in dense digraphs
• Destroying cycles in digraphs
• Digraphs
• Disjoint cycles in Eulerian digraphs and the diameter of interchange graphs
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 5032352 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• Integer Programming with a Fixed Number of Variables
• Intersection Theorems for Systems of Sets
• Kernel bounds for disjoint cycles and disjoint paths
• Kernel bounds for path and cycle problems
• Kernelization. Theory of parameterized preprocessing
• Lossy kernelization
• Minkowski's Convex Body Theorem and Integer Programming
• ON DISJOINT CYCLES
• On Independent Circuits Contained in a Graph
• On the Chudnovsky-Seymour-Sullivan conjecture on cycles in triangle-free digraphs
• Packing and covering directed triangles
• Packing arc-disjoint cycles in bipartite tournaments
• Packing arc-disjoint cycles in tournaments
• Packing directed circuits
• Parameterized algorithms
• Parameterized complexity of vertex colouring
• Parameterized tractability of edge-disjoint paths on directed acyclic graphs
• Parametrized complexity theory.
• Subquadratic kernels for implicit 3-{\textsc{Hitting Set}} and 3-{\textsc{Set Packing}} problems
• The complexity ecology of parameters: An illustration using bounded max leaf number
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity

Cited in

(1)

• A polynomial kernel for deletion to the scattered class of cliques and trees

This page was built for publication: Packing arc-disjoint cycles in oriented graphs

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