We illustrate efficient algorithms to find a maximum stable set and a maximum matching in a graph with n nodes given by the edge union of d threshold graphs on the same node set, in case the d graphs in the union are known. Actually, because the edge set of a threshold graph can be implicitly represented by assigning values to the nodes, we assume that we know these values for each of the d graphs in the union. We present an O(n log n + nd−1) time algorithm to find a maximum stable set and an O(n2) time algorithm to find a maximum matching, in case d is constant. For the case d = 2, the running time of the latter is reduced to O(n log n) provided an additional technical condition is satisfied. The natural application of our results is the fast computation of lower bounds for the d-dimensional bin packing problem, for which the compatibility relations between items are represented by the edge union of d threshold graphs with one node for each item, the value of the node for the i-th graph being equal to the size of the item on the i-th dimension.

### On d-Threshold Graphs and d-Dimensional Bin Packing

#### Abstract

We illustrate efficient algorithms to find a maximum stable set and a maximum matching in a graph with n nodes given by the edge union of d threshold graphs on the same node set, in case the d graphs in the union are known. Actually, because the edge set of a threshold graph can be implicitly represented by assigning values to the nodes, we assume that we know these values for each of the d graphs in the union. We present an O(n log n + nd−1) time algorithm to find a maximum stable set and an O(n2) time algorithm to find a maximum matching, in case d is constant. For the case d = 2, the running time of the latter is reduced to O(n log n) provided an additional technical condition is satisfied. The natural application of our results is the fast computation of lower bounds for the d-dimensional bin packing problem, for which the compatibility relations between items are represented by the edge union of d threshold graphs with one node for each item, the value of the node for the i-th graph being equal to the size of the item on the i-th dimension.
##### Scheda breve Scheda completa Scheda completa (DC)
2004
threshold graph; maximum stable set; maximum matching; d-dimensional bin packing; lower bound; computational results
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11562/409590`
• ND
• 4
• 3