Dynamic Min-Max Problems

• Ahuja, R. K., Magnanti, T. L., and Orlin, J. B. 1993. Network Flows. Prentice Hall.

• Baccelli, F., Cohen, G., Olsder, G. J., and Quadrat, J.-P. 1992. Synchronization and Linearity. New York: John Wiley, Sons.

  Google Scholar 

• Backes, W. 1994. The Structure of Longest Paths in Periodic Graphs. PhD thesis, Institut für Mikroelektronik, Universität des Saarlandes, Saarbrücken, Germany.

  Google Scholar 

• Backes, W., Schwiegelshohn, U., and Thiele, L. 1992. Analysis of free schedule in periodic graphs. 4th Annual ACM Symposium on Parallel Algorithms and Architectures, San Diego, CA, USA, pp. 333–342.

• Carlier, J., and Chretienne, P. 1988. Timed Petri Net Schedules. In LNCS Advances in Petri Nets. Springer-Verlag, vol. 340, pp. 62–84.

  Google Scholar 

• Cohen, E., and Megiddo, N. 1989. Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs (preliminary version). 21st Annual ACM Symposium on Theory of Computing, pp. 523–534.

• Cohen, G., Dubois, D., Quadrat, J. P., and Viot, M. 1985. A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing. IEEE Transactions on Automatic Control AC-30(3): 210–220.

  Google Scholar 

• Cunninghame-Green, R. A. 1962. Describing industrial processes and approximating their steady-state behaviour. Opt. Res. Quart. 13: 95–100.

  Google Scholar 

• Cunninghame-Green, R. A. 1979. Minimax algebra. In Lecture Note 166 in Economics and Mathematical Systems. Springer-Verlag, New York.

  Google Scholar 

• Even, S., and Rajsbaum, S. 1990. The use of a synchronizer yields maximum computation rate in distributed networks. 22nd Annual ACM Symposium on Theory of Computing, pp. 95–105.

• Gahlinger, T. 1990. Coherence and satisfiability of waveform timing specification. PhD thesis, University of Waterloo.

• Gunawardena, J. 1993. Timing analysis of digital circuits and the theory of min-max functions. TAU'93, ACM International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems.

• Gunawardena, J. 1994. Min-max functions. Technical Report to be published in Discrete Event Dynamic Systems, Department of Computer Science, Stanford University, Stanford, CA 94305, USA.

  Google Scholar 

• Karp, R. M. 1978. A characterization of the minimum cycle mean in a digraph. Discrete Mathematics 23: 309–311.

  Google Scholar 

• Kosaraju, S. R., and Sullivan, G. F. 1988. Detecting cycles in dynamic graphs in polynomial time (preliminary version). 20th Annual ACM Symposium on Theory of Computing, pp. 398–406.

• Lawler, E. L. 1966. Optimal cycles in doubly weighted directed linear graphs. In P. Rosenstiehl (ed.), Thèorie des Graphes, pp. 209–213.

• McMillan, K., and Dill, D. 1992. Algorithms for interface timing verification. IEEE Int. Conference on Computer Design, pp. 48–51.

• Olsder, G. J. 1991. Eigenvalues of dynamic max–min systems. Discrete Event Dynamic Systems: Theory and Applications 1: 177–207.

  Google Scholar 

• Olsder, G. J. 1993. Analyse de systèmes min-max. Technical Report 1904, Institut National de Recherche en Informatique et en Automatique.

• Orlin, J. B. 1984. Some problems in dynamic and periodic graphs. In W. R. Pulleyblank (ed.), Progress in Combinatorial Optimization. Orlando, Florida: Academic Press, pp. 215–225.

  Google Scholar 

• Ramamoorthy. C. V. 1980. Performance evaluation of asynchronous concurrent systems using Petri nets. IEEE Transactions on Software Engineering, pp. 440–449.

• Reiter, R. 1968. Scheduling parallel computations. Journal of the Association for Computing Machinery 15(4): 590–599.

  Google Scholar 

• Walkup, E. A., and Borriello, G. 1994. Interface timing verification with application to synthesis. IEEE/ACM Design Automation Conference, pp. 106–112.

• Yen, T. Y., Ishii, A., Casavant, A., and Wolf, W. 1995. Efficient algorithms for interface timing verification. Technical report, Princeton University.

• Zimmermann, U. 1981. Linear and combinatorial optimization in ordered algebraic structures. Ann. Discrete Mathematics 10: 1–380.

  Google Scholar 

Download references