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 spectral radius of (0,1)-matrices

R.A. Brualdi, 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

On bounds for eigenvalues of real symmetric matrices

E.R. Barnes, 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 spectral radius of (0,1)-matrices

On graphs whose least eigenvalue exceeds - 1 - √2

On bounds for eigenvalues of real symmetric matrices

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