Most and least uniform spanning trees (Q1087546): Difference between revisions

In so-called ''bottleneck'' combinatorial optimization problems, a family of structures is considered and one looks for a structure minimizing the maximum weight (or maximizing the minimum weight) of any component of a certain kind. For instance, the min-max spannig tree problem calls for a spanning tree where the maximum weight of any arc is minimized. This work enlarges the class of bottleneck problems by considering the difference between the maximum and the minimum weight of any component as the objective function. Both the problem of minimizing and maximizing this difference is studied. The corresponding optimum structures are called most and least uniform, respectively. Components may be single arcs or paths, graphs may or may not be directed and the arc weights may or may not be restricted to positive values. Some matroid generalizations of the above problems are also considered. In each case an efficient algorithm to achieve the optimum is presented or it is proved that the problem is NP-hard.