An Almost Linear-Time Algorithm for Graph Realization

Abstract

Given a (0, 1)-matrix M, the graph realization problem for M is to find a tree such that the columns of M are incidence vectors of paths in T, or to show that no such T exists. An algorithm is presented for this problem the time complexity of which is very nearly linear in the number of ones in M.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1985
Accession Number
ADA455177

Entities

People

  • Donald K. Wagner
  • Robert E. Bixby

Organizations

  • Rice University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Applied Mathematics
  • Engineering
  • Industrial Engineering
  • Information Operations
  • Mathematics
  • Systems Engineering

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.