11 citations · 42 across the 12 of their papers we have counts for
6 papers · 1 filter
Distributed Vertex Cover Reconfiguration
Keren Censor-Hillel, Yannic Maus, Shahar Romem-Peled +1
Reconfiguration schedules, i.e., sequences that gradually transform one solution of a problem to another while always maintaining feasibility, have been extensively studied. Most r…
Fault Tolerant Max-Cut
Keren Censor-Hillel, Noa Marelly, Roy Schwartz +1
In this work, we initiate the study of fault tolerant Max Cut, where given an edge-weighted undirected graph , the goal is to find a cut that maximizes the…
Efficient Randomized Distributed Coloring in CONGEST
Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus +1
Distributed vertex coloring is one of the classic problems and probably also the most widely studied problems in the area of distributed graph algorithms. We present a new randomiz…
Query Minimization under Stochastic Uncertainty
Steven Chaplick, Magnús M. Halldórsson, Murilo S. de Lima +1
We study problems with stochastic uncertainty information on intervals for which the precise value can be queried by paying a cost. The goal is to devise an adaptive decision tree…
Local Conflict Coloring Revisited: Linial for Lists
Yannic Maus, Tigran Tonoyan
Linial's famous color reduction algorithm reduces a given -coloring of a graph with maximum degree to a -coloring, in a single round in the LOCAL model. We sho…
Preemptive Online Partitioning of Sequences
Christian Konrad, Tigran Tonoyan
Online algorithms process their inputs piece by piece, taking irrevocable decisions for each data item. This model is too restrictive for most partitioning problems, since data tha…