Finding the Cheapest Way to Build a Graph

Abstract

The Concept Reinforcement Problem is a graph optimization problem introduced by Novikoff. One seeks to build a graph G vertex by vertex in the cheapest way possible for that graph. The cost function for each vertex is a positive, decreasing, convex function where the input is determined by the number of neighbors already built. We solve this problem for a variety of different graphs such as simple connected small-sized graphs, trees, cycles, wheels, grid graphs, ladder graphs, and complete bipartite graphs.