Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Institution
Articles 1 - 3 of 3
Full-Text Articles in Entire DC Network
Mathematical Programming And Economic Theory, Herbert E. Scarf
Mathematical Programming And Economic Theory, Herbert E. Scarf
Cowles Foundation Discussion Papers
The paper discusses the analogy between economic institutions and algorithms for the solution of mathematical programming problems. The simplex method for solving linear programs can be interpreted as a search for market prices that equilibrate the demand for factors of production with their supply. An interpretation in terms of the internal organization of the large firm is offered for Lenstra’s integer programming algorithm.
A Color-Exchange Algorithm For Exact Graph Coloring, Thomas J. Sager, Shi-Jen Lin
A Color-Exchange Algorithm For Exact Graph Coloring, Thomas J. Sager, Shi-Jen Lin
Computer Science Technical Reports
DEXCH, a color-exchange exact graph coloring algorithm is presented. On many classes of graphs, DEXCH can, in the mean, find the chromatic number of a graph considerably faster than the DSATUR algorithm. The improvement over DSATUR stems from the ability to reorganize the subset of colored vertices and to detect in certain instances the existence of a complete subgraph of cardinality equal to the number of colors used in the best coloring found so far. The mean improvement over DSATUR is greatest on high edge-density graphs attaining the value of 42% on random graphs of edge-density 0.7 on 64 vertices.
Weak Bipolarizable Graphs, Stephan Olariu
Weak Bipolarizable Graphs, Stephan Olariu
Computer Science Faculty Publications
We characterize a new class of perfectly orderable graphs and give a polynomial-time recognition algorithm, together with linear-time optimization algorithms for this class of graphs.