Negative Cycle Detection in Dynamic Graphs
| dc.contributor.author | Chandrachoodan, Nitin | en_US |
| dc.contributor.author | Bhattacharyya, Shuvra S. | en_US |
| dc.contributor.author | Liu, K.J.Ray | en_US |
| dc.date.accessioned | 2004-05-31T22:59:46Z | |
| dc.date.available | 2004-05-31T22:59:46Z | |
| dc.date.created | 1999-09 | en_US |
| dc.date.issued | 1999-10-01 | en_US |
| dc.description.abstract | We examine the problem of detecting negative cycles in a dynamic graph, which is a fundamental problem that arises in electronic design automation and systems theory. Previous approaches used for this have tried to modify Dijkstra's algorithm since it is the fastest known Single-Source Shortest Path algorithm. We introduce the concept of {\em batch mode} negative cycle detection, in which a graph changes over time, and negative cycle detection needs to be done periodically. Such scenarios arise, for example, during iterative design space exploration for hardware and software synthesis. We present an algorithm for this problem, based on the Bellman-Ford algorithm, which outperforms previous approaches. We also show that this technique leads to very fast algorithms for the computation of the maximum-cycle mean (MCM) of a graph, especially for a certain form of {\em sparse graph}. Such sparseness often occurs in practice, as demonstrated for example by the ISCAS 89/93 benchmarks. We present experimental results that demonstrate the advantages of our batch-processing techniques, and illustrate their application to design-space exploration by developing an automated local-search technique for multiple-voltage scheduling of iterative data-flow graphs. (Also cross-referenced as UMIACS-TR-99-59) | en_US |
| dc.format.extent | 1357047 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/1033 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-4065 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-99-59 | en_US |
| dc.title | Negative Cycle Detection in Dynamic Graphs | en_US |
| dc.type | Technical Report | en_US |