H. Koh
ABSTRACT
This paper describes a more restrictive definition of cutsets as they are found useful in solving certain problems and presents a reduction method to reduce a flow network (an acyclic weighted digraph) with multiple topological orderings of vertices so that (1) the resulting reduced network has only one topological ordering and (2) the original network and the reduced network have the same maximal cutset. The motivation for such a reduction method is that if a network has only one topological ordering then the maximal cutset can be found in a linear time (linear in terms of the number of arcs).
- 1.Koh, Hikyoo, "Restrictive Cutsets in a Flow Network and t h e i r Applications," submitted to Fifth International Conference on Data Engineering.Google Scholar
- 2.Koh, Hikyoo and Chuang, Henry, "Finding mal Set of Base Paths of a Program," tional Journal of Computer and Information Sciences, December 1979, pp. 473-488.Google Scholar
- 3.Horowitz, Ellis and Sahni, S., Fundamentals Data Structures, Computer Science Press, Google ScholarDigital Library
- 4.Koh, Hikyoo, "Analysis of Program Structure Test Input Generation in a Successive Environment," Ph.D. thesis, Computer Department, University of Pittsburgh, pp. 166-171. Google ScholarDigital Library
- 5.Ford, L. R. and Fulkerson, D. R., Flows works, Princeton University, 1962.Google Scholar
- 6.Papadimitriou, C. H. and Steiglitz, national Optimization, Prentice-Hall, 91-97, 117-124.Google Scholar
- 7.Koh, Hikyoo, "Partitioning Program Digraph Intervals - A Systematic Method for ting Execution Sequences," ACM Computer Conference, 1982.Google Scholar
- 8.Sedgewick, Robert, Algorithms, Addison-Wesley Publishing Company, 1988, pp. 471-489. Google ScholarDigital Library
Index Terms
- Flow network reduction for unique topological ordering
Recommendations
Topological reduction approaches for relation decision systems
AbstractIn this study, we use topological methods to investigate attribute reduction problems for relation decision systems. We propose the notions of topological consistent and inconsistent relation decision systems. Then, we propose the ...
Topological Analysis of a Complex Trust Network
ISCC '13: Proceedings of the 2013 International Conference on Information Science and Cloud ComputingIn view of the problem that the current trust models only are simulated in a simple network or a small-scale network, ignoring the macroscopic properties of trusted network, a complex trust network is built by using complex network approach and some ...
On chromatic and flow polynomial unique graphs
It is known that the chromatic polynomial and flow polynomial of a graph are two important evaluations of its Tutte polynomial, both of which contain much information of the graph. Much research is done on graphs determined entirely by their chromatic ...
Comments