A rooted-forest partition with uniform vertex demand. (English) Zbl 1274.05381
Rahman, Md. Saidur (ed.) et al., WALCOM: Algorithms and computation. 4th international workshop, WALCOM 2010, Dhaka, Bangladesh, February 10–12, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-11439-7/pbk). Lecture Notes in Computer Science 5942, 179-190 (2010).
Summary: A rooted forest is a graph having self-loops such that each connected component contains exactly one loop, which is regarded as a root, and there exists no cycle consisting of non-loop edges. In this paper, we study the partitioning of a graph into edge-disjoint rooted forests such that each vertex is spanned by exactly \(d\) components of the partition, where \(d\) is a positive integer.
For the entire collection see [Zbl 1181.68014].
For the entire collection see [Zbl 1181.68014].
MSC:
05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
05C05 | Trees |
05C85 | Graph algorithms (graph-theoretic aspects) |