Parameterized Eulerian strong component arc deletion problem on tournaments

DOI10.1016/j.ipl.2011.11.014zbMath1242.68113arXiv1106.4454OpenAlexW2166023017MaRDI QIDQ437687

J. Herrera, H. S. Yoon

Publication date: 18 July 2012

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

tournamentsgraph algorithmsfixed-parameter tractabilityEulerian digraphs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items

Editing to Eulerian graphs, A survey of parameterized algorithms and the complexity of edge modification, Parameterized Eulerian strong component arc deletion problem on tournaments

Cites Work

• Unnamed Item
• Unnamed Item
• Parameterized Eulerian strong component arc deletion problem on tournaments
• On problems without polynomial kernels
• Parametrized complexity theory.
• Computing the Deficiency of Housing Markets with Duplicate Houses
• Parameterized Complexity of Eulerian Deletion Problems
• Incompressibility through Colors and IDs
• Kernel Bounds for Disjoint Cycles and Disjoint Paths