O(|V|2) algorithm for single connectedness

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

A directed graph G = (V, E) is said to be singly connected if uqqv implies that there is at most one simple path from u to v for all vertices u, v∈V. An algorithm is designed to test a graph for being singly connected that takes O(|V|2) steps.

Original languageEnglish (US)
Pages (from-to)105-107
Number of pages3
JournalInformation Processing Letters
Volume72
Issue number3
DOIs
StatePublished - Nov 26 1999

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'O(|V|<sup>2</sup>) algorithm for single connectedness'. Together they form a unique fingerprint.

Cite this