Edge disjoint Polyp Packing Original Research Article

A graph is called a p-polyp if it consists of p simple paths of the same length and one endvertex of all these paths is a common vertex. The Polyp Packing problem is a generalization of the well-known Bin Packing problem: How to pack a set of paths with different lengths to a set of polyps edge disjointly? It is proved that the Polyp Packing problem is NP-complete and that a modification of the First-Fit algorithm gives a reasonable approximation.