Speciální případy problemu přidělování kanálů pro seriově-paralelní grafy

• Thesis title in Czech: Speciální případy problemu přidělování kanálů pro seriově-paralelní grafy
• Thesis title in English: The channel assignment problem for series-parallel graphs
• Academic year of topic announcement: 2008/2009
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: doc. RNDr. Jiří Fiala, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 13.11.2008
• Date of assignment: 13.11.2008
• Date and time of defence: 16.09.2010 00:00
• Date of electronic submission: 16.09.2010
• Date of proceeded defence: 16.09.2010
• Opponents: RNDr. Ondřej Pangrác, Ph.D.

Guidelines

Prostudovat dostupné výsledky o problému přiřazení kanálů pro třídy stromů a grafů stromové šířky 3.

Prozkoumat tzv. Theta grafy a seriově-paralelní grafy s omezenou hloubkou konstrukčního stromu.

References

Reinhard Diestel: Graph Theory, Springer-Verlag (1997)

Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad: Graph Classes: A Survey, SIAM (1999)

M. R. Garey, D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman (1979)

další časopisecká literatura dle doporučení školitele

Preliminary scope of work

Pro daný graf s ohodnocenými hranami se hledá očíslování vrcholů přirozenými čísly tak, aby rozdíl čísel přiřazených sousedním vrcholům byl alespoň tak velký, jako je předepsané ohodnocení hrany. Zároveň je třeba minimalizovat největší použité číslo.

Cílem práce je prozkoumat některé případy, kdy daný graf spadá do třídy seriově-paralelních grafů.

Preliminary scope of work in English

For a given edge-weighted graph the aim is to label vertices by nonnegative integers so the difference between labels of adjacent vertices is at least as big as the prescribed edge weight. The aim is to minimize the maximum label used.

The thesis should explore some special cases of series-parallel graphs.