JavaScript is disabled for your browser. Some features of this site may not work without it.
Browsing by Author "Tarjan, Robert Endre"
Now showing items 17 of 7

Dividing a Graph into Triconnected Components
Hopcroft, John E.; Tarjan, Robert Endre (Cornell University, 197402)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
Hopcroft, John E.; Tarjan, Robert Endre (Cornell University, 197304)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
Tarjan, Robert Endre (Cornell University, 197209)An algorithm to enumerate all the elementary circuits of a directed graph is presented. The algorithm uses backtracking with lookahead to avoid unnecessary work, and it has a time bound of $O ((V+E)(C+1))$ when applied ... 
Finding a Maximum Clique
Tarjan, Robert Endre (Cornell University, 197203)An algorithm for finding a maximum clique in an arbitrary graph is described. The algorithm has a worstcase 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
Tarjan, Robert Endre (Cornell University, 197211)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
Gilbert, John R.; Hutchinson, Joan P.; Tarjan, Robert Endre (Cornell University, 198207)Many divideandconquer 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
Tarjan, Robert Endre (Cornell University, 197301)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. ...