K. S. Thejaswini

most citedRabin Games and Colourful Universal Trees

1 citations · 1 across the 2 of their papers we have counts for

collaborators

2 papers

cs.LO2024★ 1 cited

Rabin Games and Colourful Universal Trees

Rupak Majumdar, Irmak Saglam, K. S. Thejaswini

We provide an algorithm to solve Rabin and Streett games over graphs with $n$ vertices, $m$ edges, and $k$ colours that runs in $O ~ (mn (k!)^{1 + o (1)})$ time and $O…

cs.FL2023

Simple and tight complexity lower bounds for solving Rabin games

Antonio Casares, Marcin Pilipczuk, Michał Pilipczuk +2

We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time $2^{o (k l o g k)} \cdot n^{O (1)}$ , where $k…