Brushing without capacity restrictions

Bryant, Darryn, Francetic, Nevena, Gordinowicz, Przemysław, Pike, David A. and Pralat, Paweł (2014) Brushing without capacity restrictions. Discrete Applied Mathematics, 170 33-45. doi:10.1016/j.dam.2014.01.024

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
UQ327436_OA.pdf Full text (open access) application/pdf 414.60KB 0

Author Bryant, Darryn
Francetic, Nevena
Gordinowicz, Przemysław
Pike, David A.
Pralat, Paweł
Title Brushing without capacity restrictions
Journal name Discrete Applied Mathematics   Check publisher's open access policy
ISSN 0166-218X
Publication date 2014-06-19
Year available 2014
Sub-type Article (original research)
DOI 10.1016/j.dam.2014.01.024
Open Access Status Not yet assessed
Volume 170
Start page 33
End page 45
Total pages 13
Place of publication Amsterdam, Netherlands
Publisher Elsevier
Language eng
Subject 2604 Applied Mathematics
2607 Discrete Mathematics and Combinatorics
Abstract In graph cleaning problems, brushes clean a graph by traversing it subject to certain rules. Various problems arise, such as determining the minimum number of brushes that are required to clean the entire graph. This number is called the brushing number. Here, we study a new variant of the brushing problem in which one vertex is cleaned at a time, but more than one brush may traverse a dirty edge. In particular, we obtain results on the brushing number of Cartesian products of graphs and trees, as well as upper and lower bounds on the brushing number in the general case.
Keyword Brush number
Directed path covering
Network cleaning
Q-Index Code C1
Q-Index Status Confirmed Code
Grant ID DP0770400
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: School of Mathematics and Physics
Official 2015 Collection
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 3 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 4 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 01 Apr 2014, 10:09:45 EST by System User on behalf of School of Mathematics & Physics