GFGang Feng

Gang Feng

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Latest Publications

  • Finding k shortest simple paths in directed graphs: A node classification algorithm

    by Gang Feng

    We propose a new exact algorithm for enumerating k shortest simple paths in a directed graph with n nodes and m edges. The algorithm has a complexity of and follows the same process as Yen's deviation algorithm, but the candidate paths are computed more efficiently using a node classification technique. We first show that a candidate path can be separated by its deviation node as prefix and suffix. Our algorithm then classifies the nodes as red, yellow, and green. A node on the prefix is assigned a red color, a node that can reach t (the destination node) through a shortest path without visiting a red node is assigned a green color, and all other nodes are assigned a yellow color. We prove that when searching for the suffix of a candidate path, all green nodes can be bypassed, and we only need to apply Dijkstra's algorithm to find an all‐yellow‐node subpath. Since on average the number of yellow nodes is much smaller than n, the new algorithm has a much lower average‐case running time. Experiments on many types of networks demonstrate that the new algorithm performs significantly better than existing exact algorithms that have polynomial worst‐case complexity. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(1), 6–17 2014


  • The revisit of QoS routing based on non‐linear Lagrange relaxation

    by Gang Feng

    The development of efficient quality of service (QoS) routing algorithms in a high‐speed networking or the next generation IP networking environment is a very important and at the same time very difficult task due to the need to provide divergent services with multiple QoS requirements. Recently, a heuristic algorithm H_MCOP, which is based on a non‐linear Lagrange relaxation (NLR) technique, has been proposed to resolve the contradiction between the time complexity and the quality of solution. Even though H_MCOP has demonstrated outstanding capability of finding feasible solutions to the multi‐path constrained (MCP) problem, it has not exploited the full capability that an NLR‐based technique could offer. In this paper, we propose a new NLR‐based heuristic called NLR_MCP, in which the search process is interpreted from a probability's perspective. Simulation results indicate that NLR_MCP can achieve a higher probability of finding feasible solutions than H_MCOP. We also verify that the performance improvement of a MCP heuristic has a tremendous impact on the performance of a higher level heuristic that uses a MCP heuristic as the basic step. Copyright © 2006 John Wiley & Sons, Ltd.