TY - GEN

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

AU - Mishra, B.

N1 - Funding Information:
This work was supported in part by NSF grant MCS-8216706
Publisher Copyright:
© 1984 IEEE.

PY - 1984

Y1 - 1984

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85115228844&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85115228844&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85115228844

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 207

EP - 216

BT - 25th Annual Symposium on Foundations of Computer Science, FOCS 1984

PB - IEEE Computer Society

T2 - 25th Annual Symposium on Foundations of Computer Science, FOCS 1984

Y2 - 24 October 1984 through 26 October 1984

ER -