Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 3 of 3
Full-Text Articles in Entire DC Network
Performance Modeling And Enhancement For The Atamm Data Flow Architecture, Sukhamoy Som
Performance Modeling And Enhancement For The Atamm Data Flow Architecture, Sukhamoy Som
Electrical & Computer Engineering Theses & Dissertations
Algorithm To Architecture Mapping Model (ATAMM) is a new marked graph model from which the rules for data and control flow in a homogeneous, multicomputer, data flow architecture may be defined. This research is concerned with performance modeling and performance enhancement for periodic execution of large-grain, decision-free algorithms in such an ATAMM defined architecture. Performance measures and bounds are established. Algorithm transformation techniques are identified for performance enhancement and reduction of computing element requirements. Operating strategies are developed for optimum time performance and for sub-optimum time performance under limited availability of computing elements. An ATAMM simulator is used to test …
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.