THE GRAPH-BIN PACKING PROBLEM

We deal with a very general problem: a given graph G is to be "packed" into a host graph H, and we are asked about some natural optimization questions concerning this packing. The problem has never been investigated before in this general form. The input of the problem is a simple graph G...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2011-12, Vol.22 (8), p.1971-1993
Main Authors: BUJTÁS, CSILLA, DÓSA, GYÖRGY, IMREH, CSANÁD, NAGY-GYÖRGY, JUDIT, TUZA, ZSOLT
Format: Article
Language:English
Subjects:
Algorithms
Bins
Foundations
Graphs
Joining
On-line systems
Optimization
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We deal with a very general problem: a given graph G is to be "packed" into a host graph H, and we are asked about some natural optimization questions concerning this packing. The problem has never been investigated before in this general form. The input of the problem is a simple graph G = (V, E) with lower and upper bounds on its edges and weights on its vertices. The vertices correspond to items which have to be packed into the vertices (bins) of a host graph, such that each host vertex can accommodate at most L weight in total, and if two items are adjacent in G, then the distance of their host vertices in H must be between the lower and upper bounds of the edge joining the two items. Special cases are bin packing with conflicts, chromatic number, and many more. We give some general structure statements, treat some special cases, and investigate the performance guarantee of polynomial-time algorithms both in the offline and online setting.
ISSN:0129-0541
1793-6373
DOI:10.1142/S012905411100915X