Search
Abstract
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.
Citations
-
3
CrossRef
-
0
Web of Science
-
4
Scopus
Authors (3)
-
Paweł Prałat
- Ryerson University Department of Mathematics
Cite as
Full text
download paper
downloaded 23 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.tcs.2014.09.005
- License
- Copyright (2014 Elsevier B.V.)
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
THEORETICAL COMPUTER SCIENCE
no. 557,
pages 76 - 86,
ISSN: 0304-3975 - Language:
- English
- Publication year:
- 2014
- Bibliographic description:
- Borowiecki P., Dereniowski D., Prałat p.: Brushing with additional cleaning restrictions// THEORETICAL COMPUTER SCIENCE. -Vol. 557, (2014), s.76-86
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.tcs.2014.09.005
- Verified by:
- Gdańsk University of Technology
seen 131 times