An efficient algrithm to find all 'bidirectional' edges of an undirected graph

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

An efficient algorithm for the All-Didirectional-Edgcs Problem is presented. The All-Bidirectional-Edges Problem is to find an edge-labelling of an undirected network, G = (V,E), with a source and a sink, such that an edge [u,v] ∈ E is labelled (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 orv,u, respectively. The algorithm presented works by partitioning the graph into a set of bridges and analyzing them recursively. The time complexity of the algorithm is shown to be O(|E| ·|V|). The 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, this algorithm can be used in order to detect all the sneak paths in a network of pass transistor.

Original languageEnglish (US)
Title of host publication25th Annual Symposium on Foundations of Computer Science, FOCS 1984
PublisherIEEE Computer Society
Pages207-216
Number of pages10
ISBN (Electronic)081860591X
StatePublished - 1984
Event25th Annual Symposium on Foundations of Computer Science, FOCS 1984 - Singer Island, United States
Duration: Oct 24 1984Oct 26 1984

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume1984-October
ISSN (Print)0272-5428

Conference

Conference25th Annual Symposium on Foundations of Computer Science, FOCS 1984
Country/TerritoryUnited States
CitySinger Island
Period10/24/8410/26/84

ASJC Scopus subject areas

  • General Computer Science

Fingerprint

Dive into the research topics of 'An efficient algrithm to find all 'bidirectional' edges of an undirected graph'. Together they form a unique fingerprint.

Cite this