Efficient Algorithms for Graph Manipulation,

Abstract

Efficient algorithms are presented for partitioning a graph into connected components, biconnected components and simple paths. The algorithm for partitioning of a graph into simple paths is iterative and each iteration produces a new path between two vertices already on paths. (The start vertex can be specified dynamically.) If V is the number of vertices and E is the number of edges each algorithm requires time and space proportional to max(V,E) when executed on a random access computer. (Author)

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1971
Accession Number
AD0726169

Entities

People

  • John Hopcroft
  • Robert Tarjan

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computers
  • Computing Devices
  • Iterations
  • Mathematics

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Graph Algorithms and Convex Optimization.

Technology Areas

  • Space
  • Space - Spacecraft Maneuvers