Finding Minimum Cutsets in Reducible Graphs,

Abstract

The analysis of many processes modelled by directed graphs requires the selection of a subject of vertices which cut all the cycles in the graph. Reducing the size of such a cutset usually leads to a simpler and more efficient analysis, but the problem of finding minimum cutsets in general directed graphs is known to be NP-complete. In this paper we show that in reducible graphs( and thus in almost all the practical flowcharts of programs), minmum cutsets can be found in linear time. An immediate application of this result is in program verification systems based on Floyd's inductive assertions method. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1977
Accession Number
ADA040698

Entities

People

  • Adi Shamir

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Computations
  • Computer Programs
  • Computer Science
  • Computers
  • Electronics Laboratories
  • Information Systems
  • Marine Corps
  • Mathematics
  • Military Research
  • Naval Operations
  • New York
  • Numbers
  • Security
  • Verification

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Mathematical Modeling and Probability Theory.