Faster graph algorithms via switching classes
MetadataShow full item record
The runtime of an algorithm is intimately related to how an instance is represented. Recall that the runtimes of the first generation of graph algorithms were expressed as functions of n := |V|. This analysis was natural since at this time graphs were represented in n2 space via their adjacency matrix. It was soon noticed that if m := |E| = o(n2), then a variety of graph algorithms could be sped-up by computing the adjacency-list from the adjacency matrix, then running the algorithm on the more efficient adjacency-list representation. This motivated the introduction of m to the runtime of graph ...
Showing items related by title, author, creator and subject.
Date:undatedNo. 244: Graph. Fall moisture and yield. No. 245: Graph. Use of water pounds per acre, acre feet.
USDI, Geologic Survey - Water Resources Division: Taylor Park Reservoir, Graph of Water Supply, 1963 Contributor:United States. Department of the Interior
Date:1963Taylor Park Reservoir, Graph of Water Supply, 1963. "The dam and reservoir, located about 35 miles northeast of Gunnison, are part of the Uncompahgre Project in Colorado. Recreation management at the reservoir is under the ...
Contributor:Colorado Agricultural College
Date:1927Chart titled "CO2 in Soil Air, Lysimeter 18 inches deep. Average of East and West plots. Legend: alfalfa, clover, corn, fallow."