RIOT -- The Edge Connectivity Problem

Edge Connectivity

RIOT HOME

Edge Connectivity Instructions Demo Try It!

Introduction

Network models are used to model complex real-world systems, such as telecommunications systems and transportation networks. Designers of such systems are often concerned with the reliability or stability of their designs. An important measure of a networks reliability is its arc connectivity, the minimum number of arcs whose removal from the network disconnects it into two or more components. In the telecommunications network example, an arc connectivity of two (2) would inform analysts that if only one link were severed, the network would remain functional. The arc connectivity of a network can be determined by solving an unweighted minimum two-cut problem. To determine such a cut, we solve a number of simple maximum flow/minimum cut problems using the preflow algorithm for minimum cut.

RIOT Interactive Edge Connectivity Problem

RIOT provides an interactive problem with which you may experiment. Using a simple interface, you may construct a network, and then let RIOT determine the arc connectivity. To construct a network, select the number of nodes you would like, then use the mouse button to draw them on the page. Once youve laid down your nodes, draw the connections between them. When you are finished defining your network, click the Submit button and wait for RIOT to report back with the arc connectivity information. RIOT will highlight in red a sample set of arcs whose removal will disconnect the network.

This project is made possible by Professor Dorit S. Hochbaum's ONR research grant N00014-91-J-1241.

Questions or comments? Send mail to Professor Hochbaum.

[ Edge Connectivity | Instructions | See a demo | Try It! ]

RIOT HOME