Számítástudományi és Információelméleti Tanszék

 

Témakiírás

A VLSI-huzalozás kombinatorikai algoritmusai

A nagybonyolultságú integrált áramkörök tervezésének több fázisában (elsôsorban a részletes huzalozásban) felmerülnek olyan kérdések, melyek megválaszolásához kombinatorikai, elsôsorban gráfelméleti algoritmusokra van szükség. Tipikus feladat, hogy rácspontok bizonyos részhalmazait kössük össze a rács éleibôl alkotott utakkal, fákkal; eközben a különbözô részhalmazok összeköttetését biztosító részgráfok diszjunktak legyenek. Számos ilyen problémáról tudjuk, hogy NP-teljes, azonban ezeknek is vannak polinomidôben megoldható részfeladatai. A pályázó feladata a tanszéken folyó, ilyen részfeladatok vizsgálatára vonatkozó kutatásokba való bekapcsolódás.

Irodalom:

1. T. Lengauer: Combinatorial algorithms for integrated circuit layout, Wiley, New York, 1990.

2. R. H. Möhring - D. Wagner: VLSI Network Design, Handbook in Operations Research, Elsevier, Amsterdam, 1995, 625-712

3. S. H. Gerez: Algorithms for VLSI Design Automation, Wiley, New York, 1999.

4. A. Recski: Some polynomially solvable subcases of the detailed routing problem in VLSI design, Discrete Applied Mathematics 115 (2001) 199-208.

Szükséges nyelvtudás: angol.

Dr. Recski András
egyetemi tanár
25-87
recski@cs.bme.hu