Publications Repository - Gdańsk University of Technology

In graph cleaning problems, brushes clean a graph by traversing it subject to certain rules. We consider the process where at each time step, a vertex that has at least as many brushes as incident, contaminated edges, sends brushes down these edges to clean them. Various problems arise, such as determining the minimum number of brushes (called the brush number) that are required to clean the entire graph. Here, we study a new variant of the problem in which no more than k brushes can be sent at any time step.

Authors

• dr hab. inż. Piotr Borowiecki link open in new tab ,
• prof. dr hab. inż. Dariusz Dereniowski link open in new tab ,
• Paweł Prałat