Achieves TSP space-time tradeoff with ST < 3.572 using sparse set systems admitting many maximal chains, improving prior minimum of ~3.93 and disproving a 2013 conjecture.
Bodlaender, Fedor V
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
verdicts
UNVERDICTED 3representative citing papers
Introduces exact and FPT algorithms for computing the scanwidth of DAGs and phylogenetic networks, plus a heuristic with good practical performance.
Provides complexity results for the constrained existence problem of five equilibrium notions in multiplayer graph games.
citing papers explorer
-
Improved space-time tradeoff for TSP via extremal set systems
Achieves TSP space-time tradeoff with ST < 3.572 using sparse set systems admitting many maximal chains, improving prior minimum of ~3.93 and disproving a 2013 conjecture.
-
Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
Introduces exact and FPT algorithms for computing the scanwidth of DAGs and phylogenetic networks, plus a heuristic with good practical performance.
-
Equilibria in Multiplayer Graph Games: An Algorithmic Study
Provides complexity results for the constrained existence problem of five equilibrium notions in multiplayer graph games.