A Revolutionary New Graph Algorithm and Its Development into Algorithm Engineering

A wide range of applications of the concept of flows and cuts in graphs and networks contains not only improvement of efficiency in the performance of transportations and communications but also data clustering and network reliability analysis. The reason for this is that the maximum flow problem and the minimum cut problem are two sides of the same coin due to the maximum flow minimum cut theorem, and thereby modeling using flows possesses a rich representation in many practical applications.
In fact, many cases known as an application of the maximum flow problem require us to find cuts as solutions rather than flows themselves. Nevertheless, relying on maximum flow algorithms was the formula for computing minimum cuts for long time.

In this study, a decomposition of graphs into forests that form connectivity hierarchy [1] was discovered in 1990 and an algorithm for computing a minimum cut (the edge-connectivity) {2] was designed based on the forest decomposition. The main feature of the algorithm is that it is based on the new mechanism such that after numbering the vertices in a graph by the maximum adjacency order the connectivity of the last two vertices can be detected in linear time. The emergence of an algorithm that is totally different from previously known methods in the point that minimum cuts can be computed without introducing any flows was a surprising event among researchers in the area and it made a theoretical breakthrough. From a practical point of view, it is easy to implement and it was reported that the implementation runs very fast compared with flow-based algorithms.

From these features, the algorithm has been introduced as one of the standard methods in representative text books in the field of discrete mathematics such as Cook, Cunningham, Pulleyblank, Schrijver (1998) and Korte, Vygen (2000), and has been taught in graduate/undergraduate courses in the world.

Furthermore as extensions of the minimum cut algorithm based on maximum adjacency ordering, the study systematically developed fast and elegant algorithms for solving more complex problems such as enumeration of semi-minimum cut, cactus construction problem, extreme vertex set family problem and edge-connectivity augmentation problem [3]. In particular, graph sparsification based on the forest decomposition has been well-established as one of the standard algorithm design techniques.

Theory of graph connectivity algorithms and posi-modular set functions in the study made a significant contribution for the development of a method with a high originality and establishment of a new theory system as a pioneer fundamental research which has applications in electronics and information communication. This received a great attention from the researchers in the areas of computation theory, discrete mathematics and operations research, and played as a driving force for cooperation and assimilation of these areas.

In 2010, Institute of Electronics and Communication Engineers of Japan presented the academic achievement award for the research on graph algorithms.


[1] H. Nagamochi and T. Ibaraki, "A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph, Algorithmica," Vol. 7, pp. 583-596, 1992.

[2] H. Nagamochi and T. Ibaraki, "Computing the edge-connectivity of multigraphs and capacitated graphs," SIAM J. Discrete Mathematics, Vol. 5, No.1, pp. 54-66, 1992.

[3] H. Nagamochi and T. Ibaraki, Algorithmic Aspects of Graph Connectivities, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, 2008.

Related Researches


Information Processing
(Information Processing Theory)

Events in World

no data.
Page Top