Gang Feng
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
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
Finding k shortest simple paths in directed graphs: A node classification algorithm
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
- 10 April 2006
- Published by Wiley in International Journal of Communication Systems
- Vol. 20 (1) , 9-22
The revisit of QoS routing based on non‐linear Lagrange relaxation
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.
- 10 April 2006
- Published by Wiley in International Journal of Communication Systems
- Vol. 20 (1) , 9-22
The revisit of QoS routing based on non‐linear Lagrange relaxation
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.
- 15 November 2005
- Published by Elsevier in Computer Communications
- Vol. 29 (10) , 1811-1822
A multi-constrained multicast QoS routing algorithm
- 15 November 2005
- Published by Elsevier in Computer Communications
- Vol. 29 (10) , 1811-1822
A multi-constrained multicast QoS routing algorithm
- 1 April 2005
- Published by Wiley in International Journal of Communication Systems
- Vol. 18 (7) , 671-685
Tightest constraint first: An efficient delay sensitive multicast routing algorithm
- 1 April 2005
- Published by Wiley in International Journal of Communication Systems
- Vol. 18 (7) , 671-685
Tightest constraint first: An efficient delay sensitive multicast routing algorithm