Details of Grant 

EPSRC Reference:	GR/N09855/01
Title:	PARRALEL/DISTRIBUTED COMBINATORIAL COMPUTING USING NEW TECHNOLOGIES
Principal Investigator:	Leng, Professor PH
Other Investigators:	Rytter, Professor W Gibbons, Professor A Gasieniec, Professor LA
Researcher Co-Investigators:
Project Partners:
Department:	Computer Science
Organisation:	University of Liverpool
Scheme:	Standard Research (Pre-FEC)
Starts:	24 July 2000	Ends:	23 July 2003	Value (£):	122,220
EPSRC Research Topic Classifications:	Parallel Computing
EPSRC Industrial Sector Classifications:	No relevance to Underpinning Sectors
Related Grants:
Panel History:
Summary on Grant Application Form
The project concerns fundamental algorithmic studies related to the parallel/distributed combinatorial computing. An important class SUBLIN of algorithmic problems will be identified in the project as one of the main algorithmic classes from the point of view of practical parallel/distributed computing. The relations between the class SUBLIN and the class NC will be investigated. The next important streams related to combinatorial computing are generic dynamic programming computing, new strategies for parallel/distributed backtracking and generic strategies for practical application of tree-contraction methods. An important aspect of combinatorial computing is how to narrow the space of combinatorial objects to be processed. In the context of backtracking this is related to different heuristics and in the context of dynamic programming it relies upon certain algebraic structures, e.g. Monge property of matrices. A Java-centric parallel-distributed environment and different possibilities of WWW-technology for parallel/distributed processing will be investigated. We consider a combination of the practically successful PVM system and theoretically successful abstract model of parallel Random Access Machine. The combinatorial computing is particularly well suited to experiment how to increase the computational power using parallel/distributed tools of new WWW-orientated technologies. We shall also consider the fault-tolerant issues of parallel/distributed computing
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:	http://www.liv.ac.uk