Isomorphism testing of k-spanning tournaments is fixed parameter tractable | Sciact - Система учета научной деятельности ИМ СО РАН

Isomorphism testing of k-spanning tournaments is fixed parameter tractable Научная публикация

Журнал

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

Вых. Данные

Год: 2025, Том: 8, Номер: 2, Номер статьи : 2.10, Страниц : 9 DOI: 10.26493/2590-9770.1712.3ec

Ключевые слова

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

Авторы

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

Организации

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

Поступила в редакцию:	26 окт. 2023 г.
Принята к публикации:	18 сент. 2024 г.
Опубликована online:	7 апр. 2025 г.

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

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