Degreewidth: a New Parameter for Solving Problems on Tournaments
Tom Davot, Lucas Isenmann, Sanjukta Roy, Jocelyn Thiebaut · arXiv (Cornell University) · 2022
In the paper, we define a new parameter for tournaments called degreewidth which can be seen as a measure of how far is the tournament from being acyclic. The degreewidth of a tournament $T$ denoted by $Δ(T)$ is the minimum value $k$ for which we can find an ordering $\langle v_1, \dots, v_n \rangle$ of the vertices of $T$ such that every vertex is incident to at most $k$ backward arcs (\textit{i.e.} an arc $(v_i,v_j)$ such that $j