๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Comparability graph augmentation for some multiprocessor scheduling problems

โœ Scribed by P. Dell'Olmo; M.Grazia Speranza; Zs. Tuza

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
944 KB
Volume
72
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

โœฆ Synopsis

A comparability graph is a graph which admits a transitive orientation.

In this paper we consider the problem of augmenting a graph to a comparability graph in such a way that the maximum weight of its cliques is minimum. The problem is equivalent to a multiprocessor scheduling problem and to the interval coloring problem; and in the unweighted case also to the chromatic number problem. In the general case, the problem is NP-hard in the strong sense even on some very simple types of perfect graphs. We give complexity and approximation results for two subclasses of perfect graphs, namely for split graphs and stars of cliques, for which the problem still remains intractable but admits efficient estimations.

๐Ÿ“œ SIMILAR VOLUMES

A standard task graph set for fair evalu
A standard task graph set for fair evaluation of multiprocessor scheduling algorithms
โœ Takao Tobita; Hironori Kasahara ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Springer US ๐ŸŒ English โš– 587 KB

A 'standard task graph set' is proposed for fair evaluation of multiprocessor scheduling algorithms. Developers of multiprocessor scheduling algorithms usually evaluate them using randomly generated task graphs. This makes it di cult to compare the performance of algorithms developed in di erent res

A parallel approximation scheme for the
A parallel approximation scheme for the multiprocessor scheduling problem
โœ Ricardo C. Corrรชa ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 433 KB

In this paper, a parallel branch-and-bound approach for ยฎnding approximate solutions to a general version of the multiprocessor scheduling problem is presented and analyzed. In this approach, a list heuristic and a genetic algorithm are used to ยฎnd solutions to the subproblems enumerated during the

A parallel optimization algorithm for mi
A parallel optimization algorithm for minimum execution-time multiprocessor scheduling problem
โœ Hironori Kasahara; Atsusi Itoh; Hisamitsu Tanaka; Keisuke Itoh ๐Ÿ“‚ Article ๐Ÿ“… 1992 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 944 KB

## Abstract This paper proposes a parallel optimization algorithm PDF/IHS for the minimum executionโ€time multiprocessor scheduling problem which is a strong NPโ€hard optimization problem. PDF/IHS is a parallelization and efficient implementation of the only practical optimization algorithm DF/IHS am

Some minimax problems for graphs
Some minimax problems for graphs
โœ Miroslav Fiedler ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 462 KB

Fiedler, M., Some minimax problems for graphs, Discrete Mathematics 121 (1993) 65-74. If a characteristic of a simple graph G allows an extension to nonnegative edge valuations of G, the corresponding absolute characteristic is defined as the extreme of the characteristic over all nonnegative edge