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

• Název práce v češtině: Speciální případy problemu přidělování kanálů pro seriově-paralelní grafy
• Název v anglickém jazyce: The channel assignment problem for series-parallel graphs
• Akademický rok vypsání: 2008/2009
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: doc. RNDr. Jiří Fiala, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 13.11.2008
• Datum zadání: 13.11.2008
• Datum a čas obhajoby: 16.09.2010 00:00
• Datum odevzdání elektronické podoby: 16.09.2010
• Datum proběhlé obhajoby: 16.09.2010
• Oponenti: RNDr. Ondřej Pangrác, Ph.D.

Zásady pro vypracování

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.

Seznam odborné literatury

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

Předběžná náplň práce

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ů.

Předběžná náplň práce v anglickém jazyce

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.