Fair dissections of spiders, worms, and caterpillars
Authors:
Abstract
In the present paper we deal with equipartition problems for special classes of trees, i. e., spiders, stars, worms, and caterpillars. We prove that the equipartition problem is NP‐complete for spiders (and, hence, for general trees); on the other hand, we give efficient polynomial‐time algorithms for stars, worms, and caterpillars.Keywords
This publication has 5 references indexed in Scilit:
- A Shifting Algorithm for Min-Max Tree PartitioningJournal of the ACM, 1982
- Max-Min Tree PartitioningJournal of the ACM, 1981
- A Fast Algorithm for Certain Dynamic Programming MinimizationsSIAM Journal on Applied Mathematics, 1977
- Time bounds for selectionJournal of Computer and System Sciences, 1973
- Reducibility among Combinatorial Problems1972