Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs

DOI10.1145/3196276zbMath1454.68055arXiv1706.00617MaRDI QIDQ4554366

Christophe Paul, Michał Pilipczuk, Florian Barbero

Publication date: 13 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

tournaments; cutwidth; semicomplete digraphs; kernelization theory

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C20: Directed graphs (digraphs), tournaments

68Q27: Parameterized complexity, tractability and kernelization