Edge Disjoint Polyp Packing

Katona, GY [Katona, Gyula Y. (gráfelmélet), szerző] Budapesti Műszaki Egyetem

Angol nyelvű Tudományos Szakcikk (Folyóiratcikk)
Megjelent: DISCRETE APPLIED MATHEMATICS 0166-218X 1872-6771 78 (1-3) pp. 133-152 1997
    Szakterületek:
      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.
      Hivatkozás stílusok: IEEEACMAPAChicagoHarvardCSLMásolásNyomtatás
      2022-01-26 01:34