Bidirectional Edges Problem: Part I - A Simple Algorithm

Research output: Contribution to journalArticle

Abstract

The "bidirectional edges problem" is to find an edge-labeling of an undirected network, G = (V, E), with a source and a sink, such that an edge [u, v] ∈ E is labeled 〈u, v〉 or 〈v, u〉 (or both) depending on the existence of a (simple) path from the source to sink that visits the vertices u and v, in the order u v or v, u, respectively. We provide several algorithms for this problem in the current paper and the sequel. In this paper we show the relation between this problem and the classical two-vertex-disjoint-paths problem and then devise a simple algorithm with a time complexity of O(\E\ · |V|2). In the sequel we improve the time complexity to O(\E\ · |V|). The main technique exploits a clever partition of the graph into a set of paths and bridges which are then analyzed recursively. The bidirectional edges problem arises naturally in the context of the simulation of an MOS transistor network, in which a transistor may operate as a unilateral or a bilateral device, depending on the voltages at its source and drain nodes. For efficient simulation, it is required to detect the set of transistors that may operate as bilateral devices. Also, sometimes it is intended to propagate information in one direction only, and propagation in the wrong direction (resulting in a sneak path) can cause functional error. Our algorithms can be used to detect all the sneak paths.

Original languageEnglish (US)
Pages (from-to)256-286
Number of pages31
JournalAlgorithmica (New York)
Volume15
Issue number3
DOIs
StatePublished - Mar 1996

Keywords

  • Bridge
  • Complexity
  • Cross-cut
  • Disjoint paths
  • MOS circuit
  • Pass transistor
  • Sneak path

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Bidirectional Edges Problem: Part I - A Simple Algorithm'. Together they form a unique fingerprint.

  • Cite this