Browse Prior Art Database

Computing Bi Line Connected Components of a Graph

IP.com Disclosure Number: IPCOM000086581D
Original Publication Date: 1976-Sep-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 2 page(s) / 57K

Publishing Venue

IBM

Related People

Chandra, AK: AUTHOR

Abstract

Given an undirected multigraph, there is described herein an algorithm for computing its bi-line-connected components in linear time. An undirected multigraph (henceforth called a graph) is an undirected graph in which the nodes may have self loops, and there may be more than one edge between two nodes. A graph is bi-line-connected if it either has a single node, or else, deleting one edge in the graph, will not disconnect it [1]. The bi-line-connected components of a graph are its maximal bi-line-connected subgraphs. Finding bi-line-connected components of a graph finds application in problems where graphs have to be simplified in solving some problem, as occurs in finding a set of cycle cutting nodes in a graph to efficiently answer complex queries in a relational data base [2].

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 69% of the total text.

Page 1 of 2

Computing Bi Line Connected Components of a Graph

Given an undirected multigraph, there is described herein an algorithm for computing its bi-line-connected components in linear time. An undirected multigraph (henceforth called a graph) is an undirected graph in which the nodes may have self loops, and there may be more than one edge between two nodes. A graph is bi-line-connected if it either has a single node, or else, deleting one edge in the graph, will not disconnect it [1]. The bi-line-connected components of a graph are its maximal bi-line-connected subgraphs. Finding bi-line-connected components of a graph finds application in problems where graphs have to be simplified in solving some problem, as occurs in finding a set of cycle cutting nodes in a graph to efficiently answer complex queries in a relational data base
[2].

The components of a given graph are found by performing a depth-first search [3]. Nodes in the graph are numbered as they are reached, and for any node n, LOW[n] is the smallest numbered node that can be reached from n by a path that has, at most, one "back-edge". Finding bi-line-connected components rests on the fact that a component is determined exactly when there is a node n such that LOW[n] is not less than the number assigned to n. To explicitly output the components (which are defined by sets of nodes), the nodes are stacked in NS (see the figure), and the appropriate nodes are produced from the top of NS when a component is found...