NOTES ON COVERING OF ARCS BY NODES IN AN UNDIRECTED GRAPH.

Abstract

Edmonds, Johnson, and Witzgall and Zahn have given efficient algorithms for the solution of the integer linear programming problem max z = ex s.t. Ex < f , x > 0 , x integer, where e and f are vectors with all components equal to one. (This is known as the maximum matching problem). Here the author considers 'the dual integer programming problem' (the minimal covering problem): min w = pi f s.t. pi E > e , pi integer. First a lower bound on the solution of the minimal covering is given. Then some 'cycle condition' is defined which, for some special kind of graphs (called bicactus), added as supplementary constraints to the linear programming problem will give an integer solution. Finally an algorithm is proposed to solve the minimal covering problem and a qualitative comparison of its efficiency with Gomory's method is done. (Author)

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1966
Accession Number
AD0636451

Entities

People

  • Lars-chr Lorentzen

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Computer Programming
  • Coverings
  • Efficiency
  • Evolutionary Algorithms
  • Heuristic Methods
  • Integer Programming
  • Interdisciplinary Science
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Operations Research

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research