Detta dokument överväger att partitionera hörn av ett n-vertex träd till p separata uppsättningar C1, C2,. .., Cp, kallas kluster så att antalet hörn i en kluster och antalet underträd i en kluster minimeras. För detta NP-hårda problem presenterar vi giriga heuristiker som skiljer sig åt i (i) hur delträd identifieras (med antingen en bäst passform, bra passform, eller förstklassiga urvalskriterier), (ii) om kluster fylls en i taget eller samtidigt, och (iii) hur många klusterstorlekar kan skilja sig från den idealiska storleken av c hörn per kluster, n = cp. De sista kriterierna styrs av en konstant α, 0 ≤ α < 1, så att kluster Ci För algoritmer som är resultatet av kombinationer av dessa kriterier utvecklar vi värsta fall gränser för antalet delträd i ett kluster i termer av c, α, och den maximala graden av en vertex. Vi presenterar experimentella resultat som ger insikt i hur parametrar c, α, och den maximala graden av en vertex påverkar antalet underträd och klusterstorlekar.
S.E. Hambrusch REF anser att uppdelningen av hörnen i ett n-vertexträd till p-splitter så att antalet hörn i ett kluster och antalet delträd i ett kluster minimeras.
Clustering in Trees: Optimizing Cluster Sizes and Number of Subtrees
{'venue': 'J. Graph Algorithms Appl.', 'journal': 'J. Graph Algorithms Appl.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}