On simple combinatorial optimization problems

A.J. Hoffman

doi:10.1016/0012-365X(92)90555-T

Discrete Mathematics

Paper

01 Sep 1992

On simple combinatorial optimization problems

View publication

Abstract

We characterize (0,1) linear programming matrices for which a greedy algorithm and its dual solve certain covering and packing problems. Special cases are shortest path and minimum spanning tree algorithms. © 1992.

Paper

On the distance matrix of a directed graph

R.L. Graham, A.J. Hoffman, et al.

Journal of Graph Theory

Paper

On bounds for eigenvalues of real symmetric matrices

E.R. Barnes, A.J. Hoffman

Linear Algebra and Its Applications

Paper

On graphs whose least eigenvalue exceeds - 1 - √2

A.J. Hoffman

Linear Algebra and Its Applications

Paper

Geršgorin variations III: On a theme of Brualdi and Varga

Endre Boros, Richard A. Brualdi, et al.

Linear Algebra and Its Applications

View all publications

Abstract

Related

On the distance matrix of a directed graph

On bounds for eigenvalues of real symmetric matrices

On graphs whose least eigenvalue exceeds - 1 - √2

Geršgorin variations III: On a theme of Brualdi and Varga