The Complexity of Reliability Computations in Planar and Acyclic Graphs.

Abstract

The author shows that the problem of computing source-sink reliability is NP-hard, in fact P-complete, even for undirected and acyclic directed source-sink planar graphs having vertex degree at most three. Thus the source-sink reliability problem is unlikely to have an efficient algorithm, even when the graph can be laid out on a rectilinear grid. Keywords include: Reliability; complexity; planar graph; acyclic graph; NP-hard; P-complete.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1984
Accession Number
ADA150759

Entities

People

  • J. S. Provan

Organizations

  • University of North Carolina at Chapel Hill

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Algorithms
  • Automata
  • Classification
  • Coefficients
  • Computations
  • Crossings
  • Equations
  • North Carolina
  • Numbers
  • Operations Research
  • Polynomials
  • Probability
  • Rational Numbers
  • Reliability
  • Scientific Research

Fields of Study

  • Engineering

Readers

  • Graph Algorithms and Convex Optimization.