Browse Prior Art Database

Cycle Cutting Algorithm for Undirected Graphs

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

Publishing Venue

IBM

Related People

Chandra, AK: AUTHOR

Abstract

An undirected multigraph is an undirected graph in which nodes may have self loops (edges connecting a node to itself) and there may be more than one edge between two nodes. Finding a small set S of nodes that cut all cycles finds application in optimizing queries on a relational data base. Reference [1] describes an algorithm for answering a query in time about r/s/ where r is the maximum number of elements in a relation, and s is the size of the cycle-cutting set of a graph corresponding to the query. Since r is usually large, decreasing s as much as possible is important.

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 55% of the total text.

Page 1 of 4

Cycle Cutting Algorithm for Undirected Graphs

An undirected multigraph is an undirected graph in which nodes may have self loops (edges connecting a node to itself) and there may be more than one edge between two nodes. Finding a small set S of nodes that cut all cycles finds application in optimizing queries on a relational data base. Reference [1] describes an algorithm for answering a query in time about r/s/ where r is the maximum number of elements in a relation, and s is the size of the cycle-cutting set of a graph corresponding to the query. Since r is usually large, decreasing s as much as possible is important.

One way of choosing a minimal set is to enumerate all subsets of the set of nodes to find the smallest cycle-cutting set. this can take time about n! (n factorial) where n is the number of nodes in the graph. No algorithm is known for finding a minimal set in better than exponential time. A fast algorithm is described for picking a small, though not necessarily minimal, set.

In the present algorithm, the steps below are applied until none is applicable.

L1. If a node has a self loop, add this node to the set S and delete it from the graph.

L2. If a node has a single edge incident on it, delete the node. L3. If a node has two edges incident on it, add an edge between its two neighbors (even if both are the same node) and

delete it.

L4. If two nodes are directly connected to each other by more than two edges, delete all but two of these edges.

L5. Separate the graph into bi-line-connected components. L6. If a node A (Fig. 1) is directly connected to a node B (B Not = A) by an edge e, and B

cycle dominates a (every cycle through A passes through B),

then if A(1),...,A(n) are the nodes connected to

A by edges other than e, add an edge connecting B to each of

A(1),e...A(n) and delete A (comment: one of the A(i)'s

may be B.

If steps L1-L6 reduce the graph to an empty graph, the set S is minimal. Otherwise, apply step L7 repeatedly until the graph becomes empty, then apply L8.

L7. Pick a node of maximal degree (maximum number of edges incident on it), add it to the set S and delete it from

the graph. Then apply L1-L6 until none is applicable.

L8. One b...