Minimum Cycle Covering and Integer Flows

Abstract

It was conjectured by Fan that if a graph G = (V,E) has a nowhere- zero 3-flow, then G can be covered by two even subgraphs of total size at most / V/ + /E/ -3. This conjecture is proved in this paper. It is also proved in this paper that the optimum solution of the Chinese Postman problem and the solution of minimum cycle covering problem are equivalent for any graph admitting a nowhere-zero 4-flow.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 15, 1989
Accession Number
ADA216546

Entities

People

  • Cun-quan Zhang

Organizations

  • West Virginia University

Tags

Communities of Interest

  • Counter IED

DTIC Thesaurus Topics

  • Abstracts
  • Availability
  • Coverings
  • Diameters
  • Mathematics
  • Notation
  • Orientation (Direction)
  • Scientific Research
  • Universities
  • Virginia
  • West Virginia

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research