𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Path-isomorphic networks

✍ Scribed by David Hartvigsen

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
692 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Two source‐sink (directed) networks are called path‐isomorphic if there exists a bijection π between their arc sets that preserves (simple) source‐sink directed paths. Although path‐isomorphic networks need not be isomorphic (they need not even have the same number of nodes), we show that several properties are preserved. For example, suppose N and N′ are path‐isomorphic. Then, N is acyclic if and only if N′ is acyclic. B is the arc set of block of N if and only if π(B) is the arc set of a block of N′. Also, D is the arc set of a dicomponent of N if and only if π(D) is the arc set of a dicomponent of N′. In addition, we prove a dipath version of Whitney's well‐known 2‐isomorphism theorem for a special class of networks, which includes the acyclic networks.

📜 SIMILAR VOLUMES

Tellegen's theorem for 2-isomorphic netw
Tellegen's theorem for 2-isomorphic networks
✍ Cel, J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 51 KB

Let N and N I be directed networks having the same number of branches labelled correspondingly. It is proved that one of them can be reorientated so that u2 i "i2u for all vectors of corresponding branch voltages u, u and currents i, i satisfying Kirchhoff 's voltage and current law in every loop an

The Isomorphism Problem For Directed Pat
The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
✍ L. Babel; I.N. Ponomarenko; G. Tinhofer 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 237 KB

This paper deals with the isomorphism problem of directed path graphs and rooted directed path graphs. Both graph classes belong to the class of chordal graphs, and for both classes the relative complexity of the isomorphism problem is yet unknown. We prove that deciding isomorphism of directed path

Packet path assurance for IP networks
Packet path assurance for IP networks
✍ Steven Makowski; Anwar Walid; Indra Widjaja 📂 Article 📅 2006 🏛 Institute of Electrical and Electronics Engineers 🌐 English ⚖ 214 KB 👁 1 views

This paper proposes a fast and simple technique, called packet path assurance (PPA) test, for admission control in packet networks that provide multimedia applications such as Voice over IP (VoIP). The distinctive features of the PPA test are that it uses active probes to evaluate the quality of the

Shortest-Path Routing in Arbitrary Netwo
Shortest-Path Routing in Arbitrary Networks
✍ Friedhelm Meyer auf der Heide; Berthold Vöcking 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 197 KB

We introduce an on-line protocol which routes any set of N packets along shortest paths with congestion C and dilation D through an arbitrary network in Ž . O C q D q log N steps, with high probability. This time bound is optimal up to the additive log N, and it has previously only been reached for