Ajay Saju Jacob

dblp:257/1390 · DBLP profile ↗
← Back
2ranked-venue papers
1as first author
1since 2021 · last 2024
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 1 first-author · 1 since 2021
YearPublicationVenuePosition
2024 Packing arc-disjoint cycles in oriented graphs
abstract
Arc-Disjoint Cycle Packing is a classical NP -complete problem and we study it from two perspectives: (1) by restricting the cycles in the packing to be of a fixed length, and (2) by restricting the inputs to bipartite tournaments. Focusing first on Arc-Disjoint r -Cycle Packing (where the cycles in the packing are required to be of length r ), we show NP -completeness in oriented graphs with girth r for each r ≥ 3 and study the parameterized complexity of the problem with respect to two parameterizations (solution size and vertex cover size) for r = 4 in oriented graphs. Moving on to Arc-Disjoint Cycle Packing in bipartite tournaments, we show that every bipartite tournament either contains k arc-disjoint cycles or has a feedback arc set of size at most 7 ( k − 1 ) . This result adds to the set of Erdös-Pósa-type results known in the combinatorics literature for packing and covering problems.
Jasine Babu, Ajay Saju Jacob, R. Krithika 0001, Deepak Rajendraprasad
J. Comput. Syst. Sci.2
2020 Packing Arc-Disjoint Cycles in Bipartite Tournaments
Ajay Saju Jacob, R. Krithika 0001
WALCOM1