Isomorphism testing of $k$-spanning tournaments is Fixed Parameter Tractable

Autor:	Arvind, Vikraman, Ponomarenko, Ilia, Ryabov, Grigory
Rok vydání:	2022
Předmět:	Mathematics - Combinatorics Computer Science - Computational Complexity Computer Science - Data Structures and Algorithms 05C20 05C60 05C85
Druh dokumentu:	Working Paper
Popis:	An arc-colored tournament is said to be $k$-spanning for an integer $k\geq 1$ if the union of its arc-color classes of maximal valency at most $k$ is the arc set of a strongly connected digraph. It is proved that isomorphism testing of $k$-spanning tournaments is fixed-parameter tractable. Comment: 8 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2201.12312 Zobrazit plný text záznamu View this record from Arxiv