2005-02: Integer Programming Methods for Several Optimization Problems in Graph Theory

DIMACS TR: 2005-02

Integer Programming Methods for Several Optimization Problems in Graph Theory

Authors: Jamiru Luttamaguzi, Michael Pelsmajer, Zhizhang Shen and Boting Yang

ABSTRACT
In this paper, we discuss how to solve several graph theory based optimization problems by following an {\em integer programming} approach. In particular, we discuss such problems as the space-filling problem, the bandwidth problem, the cut-width problem, and the feedback edge/vertex problem. We present respective IP formulations, and carry out some preliminary output analysis.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-02.ps.gz

DIMACS Home Page