Course Code |
MATE 8031 |
---|---|

Course Title |
Combinatorial Optimization I |

Credits |
3 |

Hours |
3 per week |

Prerequisites |
MATH 6881, MATH 8001 |

Description |
Elements of linear and integer programming: branch and bound methos and its application to combinatorial optimization problems. Network flow theory and its generalizations: statistical maximal flow, feasibility theorems and combinatorial applications, minimal cost flow problems, multi-terminal maximal flows, multi-commodity flows. Matching theory and its generalizations: matchings in bipartite graphs, size and structure of maximum matchings, bipartite graphs with perfect matchings, general graphs with perfect matchings, some graph-theoretical problems related to matchings, matchings and linear programming, matching algorithms, the f-factor problem, vertex packing and covering, some generalizations of matching problems. |

Additional Information |