24 citations · 29 across the 15 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.DM2020
Unified greedy approximability beyond submodular maximization
Yann Disser, David Weckbecker
We consider classes of objective functions of cardinality constrained maximization problems for which the greedy algorithm guarantees a constant approximation. We propose the new c…
cs.DS2020
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
Jiehua Chen, Wojciech Czerwiński, Yann Disser +8
We present a data structure that in a dynamic graph of treedepth at most , which is modified over time by edge insertions and deletions, maintains an optimum-height elimination…
cs.DS2020
Improved Lower Bound for Competitive Graph Exploration
Alexander Birx, Yann Disser, Alexander V. Hopp +1
We give an improved lower bound of 10/3 on the competitive ratio for the exploration of an undirected, edge-weighted graph with a single agent that needs to return to the starting…