Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
The directed temporal exploration problem
Marcelo Garlet Milani, Lucas Picasarri-Arrieta, Chaoliang Tang +1
We study the temporal exploration problem on temporal digraphs. We prove that a lifetime of suffices to guarantee the existence of a temporal exploration on always-unilate…
cs.DS2026
Hardness and Approximation for Coloring Digraphs
Parinya Chalermsook, Harmender Gahlawat, Felix Klingelhoefer +2
The dichromatic number of a digraph is the minimum number such that can be partitioned into subsets, each inducing an acyclic digraph. The acyclic number…
cs.DS2025
A Polynomial-Time Approximation Algorithm for Complete Interval Minors
Romain Bourneuf, Julien Cocquet, Chaoliang Tang +1
As shown by Robertson and Seymour, deciding whether the complete graph is a minor of an input graph is a fixed parameter tractable problem when parameterized by . From…