Triangle packing in (sparse) tournaments: approximation and kernelization

DOI10.4230/LIPIcs.ESA.2017.14zbMath1442.68160arXiv1707.04220OpenAlexW2963920736MaRDI QIDQ5111699

Marin Bougeret, Jocelyn Thiebaut, Stéphane Bessy

Publication date: 27 May 2020

Full work available at URL: https://arxiv.org/abs/1707.04220

zbMATH Keywords

approximation algorithmsparameterized algorithmsfeedback arc settournament triangle packing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (3)

Packing arc-disjoint cycles in tournaments ⋮ Packing Arc-Disjoint Cycles in Tournaments ⋮ Tournaments and Semicomplete Digraphs

Cites Work

• Complementary cycles in regular bipartite tournaments: a proof of Manoussakis, Song and Zhang conjecture
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• A Problem Kernelization for Graph Packing
• A Quadratic Kernel for 3-Set Packing
• A 7/3-Approximation for Feedback Vertex Sets in Tournaments
• Properties of vertex packing and independence system polyhedra
• Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT
• A Min-Max Theorem on Feedback Vertex Sets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Triangle packing in (sparse) tournaments: approximation and kernelization