An Algorithm to Minimize Memory Usage in Graph-based Applications

Overview

Objectives/Goals The objective of this project was to invent an efficient algorithm to minimize the memory usage of software applications that use graph data structures. Based on analysis of possible approaches to solving the problem, it was hypothesized that an optimum algorithm could run in approximately O (S^2*E) time, S and E being the number of sources and number of edges in an input graph, respectively. A heuristic algorithm was considered an acceptable solution if its runtime benefits over optimum algorithms outweighed its lack of consistent optimality. Methods/Materials To minimize its memory usage, a graph-based application must dynamically free memory used by graph edges and vertices that are no longer reachable by any sources yet to be traversed. In this context, the weight of a graph edge is assumed to indicate the amount of memory being used by data stored as part of the edge. A graph's average weight is defined as the average of S graph weights, the total weight of the graph being taken after each source traversal. An algorithm that optimally frees memory used by graph edges is defined as one that produces for any input graph a source ordering that enables minimization of the graph's average weight. Use of the average weight system allows early elimination of significant graph weight to be valued highly, an important factor in producing optimum results. A brute force algorithm that checks all possible orderings of a graph's sources was developed to verify algorithm optimality. Results The proposed algorithm uses recursion to find the optimum source ordering of an input graph; it divides the graph into smaller and smaller subgraphs until it reaches a base case and then works its way back up, eventually returning to and solving for the original input graph. The algorithm is a heuristic that produced optimum results for most tested graphs; it has sizable runtime benefits over considered optimum algorithms. Analysis shows that the algorithm runs in approximately O (S^4*V*log E) time. Conclusions/Discussion The major contributions of this work to the field of graph theory are the definition and implementation of the concepts of average graph weight and optimum source ordering for dynamic graph weight minimization. In addition to its applications in improving software efficiency, the proposed algorithm has numerous other practical uses. Most notable among them is its ability to minimize energy usage in factories.

Awards (1)

• Third Place

Competition history

• CSEF 2008 Mathematics & Software · Entry J1321

Resources

• CSEF project summary ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

• All Computational Sciences projects
• CSEF Computational Sciences projects
• Every CSEF 2008 project
• CSEF Third Place winners