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

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

Post by jorda » Tue, 01 Jun 2004 03:57:34


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.

Thanks in advance,
Jordan Samuels
 
 
 

1. ~WET~Kintai Bridge-- Kintai Bridge, Yamaguchi Prefecture, Japan.jpg [1/2]

2. "Bridge Connection" or "Network Bridges"...

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">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content="MSHTML 6.00.2800.1400" name=GENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=#ffffff>
<DIV><FONT face=Arial size=2>Hello!!</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>Somebody knows some<STRONG> Software</STRONG> or
some way to make a "Bridge Connection" or "Network Bridges" between two
Network Adapters (in same computer) in Windows 98SE?</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>Thanks!!!!!!!</FONT></DIV></BODY></HTML>

3. Network adapters bridged but MAC Bridge Miniport does not show

4. Can I bridge without a bridge?

5. [PATCH] acpi bridge hotadd: Fix pci_enable_device() for p2p bridges

6. [Bridge] [BUG] Dropping fragmented IP packets within VLAN frames on bridge

7. [Bridge] [BUG] Dropping fragmented IP packets within VLAN frames on bridge

8. Bridge/workgroup bridge scenario and channels

9. "Bridge Connection" or "Network Bridges"...

10. NIC Shows Bridged, but No Bridge Active

11. sudden network problem with "bridge" "bridging"

12. Wireless bridge using XP bridge on laptop - can't get it to work!

13. Network adapters bridged but MAC Bridge Miniport does not show up

14. Tell me what is bridge mode and half bridge mode of adsl routers

15. [PATCH] bridge-utils: fix sysfs path for setting bridge configuration parameters