Isomorphism testing of k-spanning tournaments is fixed parameter tractable

Isomorphism testing of k-spanning tournaments is fixed parameter tractable Full article

Journal

Art of Discrete and Applied Mathematics
, E-ISSN: 2590-9770

Output data

Year: 2025, Volume: 8, Number: 2, Article number : 2.10, Pages count : 9 DOI: 10.26493/2590-9770.1712.3ec

Tags

Graph isomorphism problem, colored tournaments, fixed-parameter tractable algorithm

Authors

Arvind Vikraman ¹ , Ponomarenko Ilia ² , Ryabov Grigory ^3,4

Affiliations

1	The Institute of Mathematical Sciences (HBNI)
2	St. Petersburg Department of V.A. Steklov Institute of Mathematics
3	Ben Gurion University of the Negev
4	Novosibirsk State Technical University

Anarc-colored tournament is said to be k-spanning for an integer k ≥ 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.

Arvind V. , Ponomarenko I. , Ryabov G.
Isomorphism testing of k-spanning tournaments is fixed parameter tractable
Art of Discrete and Applied Mathematics. 2025. V.8. N2. 2.10 :1-9. DOI: 10.26493/2590-9770.1712.3ec Scopus OpenAlex

Submitted:	Oct 26, 2023
Accepted:	Sep 18, 2024
Published online:	Apr 7, 2025

Scopus:	2-s2.0-105005755481
OpenAlex:	W4405461698

Пока нет цитирований