Now showing items 1-7 of 7

• #### Dividing a Graph into Triconnected Components ﻿

(Cornell University, 1974-02)
An algorithm for dividing a graph into triconnected components is presented. When implemented on a random access computer, the algorithm requires \$O(V+E)\$ time and space to analyze a graph with \$V\$ vertices and \$E\$ edges. ...
• #### Efficient Planarity Testing ﻿

(Cornell University, 1973-04)
This paper describes an efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane. The algorithm may be viewed as an iterative version of a method originally proposed by Auslander and Parter ...
• #### Enumeration of the Elementary Circuits of a Directed Graph ﻿

(Cornell University, 1972-09)
An algorithm to enumerate all the elementary circuits of a directed graph is presented. The algorithm uses back-tracking with lookahead to avoid unnecessary work, and it has a time bound of \$O ((V+E)(C+1))\$ when applied ...
• #### Finding a Maximum Clique ﻿

(Cornell University, 1972-03)
An algorithm for finding a maximum clique in an arbitrary graph is described. The algorithm has a worst-case time bound of \$k(1.286)^{n}\$ for some constant \$k\$, where \$n\$ is the number of vertices in the graph. Within a ...
• #### On the Efficiency of a Good but Not Linear Set Union Algorithm ﻿

(Cornell University, 1972-11)
Consider two types of instructions for manipulating disjoint sets. FIND(x) computes the name of the (unique) set containing element x. UNION(A,B,C) combines sets A and B into a new set named C. We examinee a known algorithm ...
• #### A Separator Theorem for Graphs of Bounded Genus ﻿

(Cornell University, 1982-07)
Many divide-and-conquer algorithms on graphs are based on finding a small set of vertices or edges whose removal divides the graph roughly in half. Most graphs do not have the necessary small separators, but some useful ...
• #### Testing Flow Graph Reducibility ﻿

(Cornell University, 1973-01)
Many problems in program optimizationn have been solved by applying a technique called interval analysis to the flow graph of the program. A flow graph which is susceptible to this type of analysis is called reducible. ...