Isomorphism testing of k-spanning tournaments is Fixed Parameter Tractable

MaRDI QIDQ6389512zbMATH OpenFDO

Authors Vikraman Arvind, Ilya Ponomarenko, Grigoriĭ Konstantinovich Ryabov

Publication date 28 January 2022

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: An arc-colored tournament is said to be $k$-spanning for an integer $kgeq1$ 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.

This page was built for publication: Isomorphism testing of $k$-spanning tournaments is Fixed Parameter Tractable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6389512)