## Variant of bridge-finding algorithm for "n-bridges"

### Variant of bridge-finding algorithm for "n-bridges"

I'm curious to know if anyone has done work on an extension of
bridge-finding for undirected graphs. I have a notion of "n-bridges"
which is as follows: a 1-bridge is a bridge in the usual sense: its
removal increases the number of connected components of the graph.
Continue the definition in the obvious way: a 2-bridge is an edge
whose removal increases the number of 1-bridges, and similarly an
n-bridge is an edge whose removal increases the number of
(n-1)-bridges.

Note that in general the increase in (n-1)-bridges may be by more than
one. (Consider, for example, a complete graph on 3 nodes, in which
each edge is a 2-bridges whose removal increases the number of
1-bridges from 0 to 2.)

Does anyone know of an extension to algorithms such as Tarjan's which
could (somewhat efficiently) generate the list of k-bridges for a
graph, where k ranges from 1 to n for some moderately-sized n?

One application of this algorithm would be to use the k-bridges to
identify "k-connected components" of the graph. This would be
particularly useful in certain areas of analysis of program complexity
and partitioning. Imagine that modules (e.g. classes) of a program
have a dependency (or invocation) graph that has no bridges, but has
perhaps several 2-, 3- or 4-bridges. The 4-connected components of
the graph would give some insight into possible decoupling strategies
for the program which are not available by simple decouplings of
single 1-bridges.

Jordan Samuels

This is a multi-part message in MIME format.

Hello!!

Somebody knows some Software or some way to make a "Bridge Connection" or "Network Bridges" between two Network Adapters (in same computer) in Windows 98SE?

Thanks!!!!!!!
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">