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

From: Jordan Samuels (jordan_at_madsam.com)
Date: 05/30/04

  • Next message: Lance Lamboy: "Re: P vs. NP Problem; 1WayFx Model a possible solution." 
    Date: 30 May 2004 11:57:34 -0700

    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

  • Next message: Lance Lamboy: "Re: P vs. NP Problem; 1WayFx Model a possible solution."