| EPSRC Reference: |
GR/L81468/01 |
| Title: |
DESIGN ,ANALYSIS,& IMPLEMENTATION OF ALGORITHMS FOR NETWORK FLOW PROBLEMS |
| Principal Investigator: |
Radzik, Professor T |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
Kings College London |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
16 March 1998 |
Ends: |
15 September 2001 |
Value (£): |
140,773
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
|
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
This research focuses on the design, analysis and implementation of algorithms for the multicommodity flow problem, the generalised flow problem and other related network flow problems. Such problems arise in situations when the general goal is to design flow of a commodity, or a number of commodities, through a common underlying network. A wide range of areas where network flow problems have applications include computer networking, telecommunications, scheduling and routing, transportation, and financial analysis. Since the size of networks appearing in applications grow rapidly, there is a constant demand for ever more efficient network flow algorithms. The general objective of our research is to improve efficiency and scalability of algorithmic techniques for network flow problems. Our approach is to combine thorough investigation of combinatorial structures of the underlying networks with the elements of the interior-point method developed for linear programming. An important part of this project is development of implementation of recently proposed algorithms for the multicommodity flow and the generalised flow. We will use the developed software in extensive experimental study to evaluate the practical performance of implemented algorithms. For the experiments we will develop classes of input networks which reflect properties of networks arising in various application areas.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
|